Wednesday, December 14, 2016

UVA 280 - Vertex

#include<bits/stdc++.h>
using namespace std;
vector<int>adj[105];
bool vis[105];
void bfs(int s , int nodes)
{
    fill(vis,vis+nodes,false);
    queue<int>q;
    while(!q.empty())q.pop();
    q.push(s);
    while(!q.empty()){
        int fr = q.front();
        q.pop();
        for(int i = 0; i < adj[fr].size(); i++){
            if(!vis[adj[fr][i]]){
                vis[adj[fr][i]] = true;
                q.push(adj[fr][i]);
            }

        }

    }
    int cnt = 0;
    for(int i=0; i<nodes; i++){
        if(!vis[i])cnt++;
    }
    cout <<cnt;
    for(int i=0; i<nodes; i++){
        if(!vis[i])cout <<' '<<i+1;
    }
    cout << '\n';

}

int main()
{
    int nodes;
    while(cin >> nodes && nodes){

        memset(adj,0,sizeof adj);

        int i;
        while(cin >> i && i){
            int j;
            while( cin >> j && j){
                adj[i-1].push_back(j-1);
            }
        }
        int t;
        cin >> t;
        while(t--){
            int query;
            cin >> query;
            bfs(query-1 , nodes);
        }

    }

return 0;
}

No comments:

Post a Comment