Cod sursa(job #1144307)

Utilizator BlueStrutAndrei Prahoveanu BlueStrut Data 16 martie 2014 21:28:59
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<cstdio>
#include<deque>
#include<cstring>
using namespace std;
deque<int> g[100002];
int i, n, x, y, nr, k;
bool t[100002];
void marcheaza(int x) {
    int p;
    deque<int>::iterator it;
    for (it=g[i].begin();it!=g[i].end();it++) {
        p=(int)*it;
        if (t[p]==false) {
            t[p]=true;
            marcheaza(p);
        }
    }
}
int main(){
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d%d", &n, &k); nr=0;
    for (i=1;i<=k;i++) {
        scanf("%d%d", &x, &y); g[x].push_back(y); g[y].push_back(x);
        t[i]=false;
    }
    for (i=1;i<=n;i++) if (t[i]==false) {
        t[i]=true; nr++;
        marcheaza(i);
    }
    printf("%d", nr); return 0;
}