Cod sursa(job #1726803)

Utilizator dominiciorgandaDominic Iorganda dominiciorganda Data 9 iulie 2016 04:06:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;
vector<int>f[100005];
int k,i,m,x,j,g[100005],x1,x2,m1,ct,ct1;
bool h[100005];
queue<int>q;
int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d%d",&x,&m);
    for(k=1;k<=m;k++)
    {
        scanf("%d%d",&i,&j);
        f[i].push_back(j);
        f[j].push_back(i);
    }
    for(k=1;k<=x;k++)
        g[k]=1;
    for(k=1;k<=x;k++)
    {
        if(g[k])
        {
            ct++;
        for(q.push(k),g[k]=0;!q.empty();q.pop())
    {
        m1=f[q.front()].size();
        for(i=0;i<m1;i++)
        {
            if(g[f[q.front()][i]])
            {
                g[f[q.front()][i]]=0;
                q.push(f[q.front()][i]);
            }
        }
    }
        }
    }
    printf("%d\n",ct);
    return 0;
}