Cod sursa(job #1226263)

Utilizator BlueStrutAndrei Prahoveanu BlueStrut Data 4 septembrie 2014 22:58:53
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
vector<int> g[100001];
int i, n, x, y, nr, k;
bool t[100002];
int min(int a, int b){if (a<=b) return a; else return b;}
int max(int a, int b){if (a>=b) return a; else return b;}
void marcheaza(int x) {
    int p;
    vector<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[min(x, y)].push_back(max(x, y));
        t[i]=false;
    }
    for (i=1;i<=n;i++) if (t[i]==false) {
        t[i]=true; nr++;
        marcheaza(i);
    }
    printf("%d", nr); return 0;
}