Submission #11379165

---

Source Code Expand

#include<iostream>
#include<vector>
#include<cstring>
#include<set>
using namespace std;

class Graph{

    public:
    int V;
    
    // adjacency list of friends of every user(node)
    vector<int> *frend;
    
    // adjacency list of blocks of every user(node)
    vector<int> *block;

    set<int> component;

    Graph(int vertices){
        V=vertices;
        frend = new vector<int>[vertices];
        block = new vector<int>[vertices];
    }

    void addfriend(int p, int q){
        frend[p].push_back(q);
        frend[q].push_back(p);
    }

    void addblock(int p, int q){
        block[p].push_back(q);
        block[q].push_back(p);
    }

    int DFS(int v, bool *visited){

        visited[v]=true;
        component.insert(v);
        int count=1;
        vector<int>::iterator it;
        for(it=frend[v].begin(); it!=frend[v].end(); it++){
            if(!visited[*it]){
                count+=(DFS(*it,visited));
            }
        }
        return count;
    }

};

int main(){

    int n, m, k;
    cin >> n >> m >> k;

    Graph g(n);
    while (m--)
    {
        int u, v;
        cin >> u >> v;
        // subtracting 1 because in the graph the array will have addresses from 0 to n-1(means node-1 is node-0 and node-n is node-(n-1))
        u=u-1;
        v=v-1;
        g.addfriend(u,v);
    }
    
    while (k--)
    {
        int u, v;
        cin >> u >> v;
        u=u-1;
        v=v-1;
        g.addblock(u,v);
    }

    bool *visited = new bool[n];
    memset(visited,false,sizeof visited);

    // answer for every node-
    int ans[n]={};

    for(int i=0; i<n; i++){

        if(!visited[i]){

            g.component.clear();
            int comp_size=g.DFS(i,visited);

            set<int>::iterator itr;

            // iterating the large component and assigning the answer to every node in that component.
            for(itr=g.component.begin();itr!=g.component.end();itr++){

                ans[*itr]=(comp_size-1); // removing the node itself.
                ans[*itr]-=(g.frend[*itr].size()); // removing friends.

                // checking how many block node by i-th user has in the component.
                vector<int>::iterator it;
                for(it=g.block[*itr].begin(); it!=g.block[*itr].end(); it++){
                    if(g.component.count(*it)) ans[*itr]--;
                }
            }
        }
    }
    for(int i=0; i<n; i++) cout << ans[i] << " ";
    cout << "\n";
    return 0;
}

Submission Info

Judge Result