Cod sursa(job #2222520)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 17 iulie 2018 10:43:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int NMAX = 100000;
vector<int> G[NMAX + 5];
vector<int> viz;
vector<int>::iterator it;

ifstream cin("dfs.in");
ofstream cout("dfs.out");

void bfs(int u, int cc)
{
    queue<int> q;
    int v;
    viz[u] = cc;
    q.push(u);
    while(!q.empty())
    {
        u = q.front(); q.pop();
        for(it = G[u].begin(); it != G[u].end(); it++)
        {
            v = *it;
            if(!viz[v])
            {
                viz[v] = cc; q.push(v);
            }
        }
    }
}

int main()
{
    int n, m, i, u, v, cc, j;
    cin>>n>>m;
    for(i = 1; i <= m; i++)
    {
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    viz.assign(n+1, 0);
    cc = 0;
    for(i = 1; i <= n; i++)
    {
        if(!viz[i])
        {
            cc++;
            bfs(i, cc);
        }
    }
    cout<<cc<<"\n";
    /*for(i = 1; i <= cc; i++)
    {
        for(j = 1; j <= n; j++)
            if(viz[i] == cc)
                cout<<j<<" ";
        cout<<"\n";
    }*/
    return 0;
}