Cod sursa(job #283430)

Utilizator d0d0Hoaghea Teodor-Andrei d0d0 Data 19 martie 2009 09:47:32
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<iostream.h>
#include<fstream.h>
#include<stdio.h>
int i,j,v[1000][1000],n,m,c,k,s[1000],g,q=0;
void df(int nod){
    int c;
    s[nod]=1;
    for(c=1;c<=n;c++)
        if(v[nod][c]==1 && s[c]==0)
            df(c);
}
int main(){
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
    scanf("%d",&n);
    scanf("%d",&m);
    for(k=1;k<=n;k++)
        for(g=1;g<=n;g++)
            v[k][g]=0;
    for(k=1;k<=m;k++){
        scanf("%d",&i);
        scanf("%d",&j);
        v[i][j]=1;
        v[j][i]=1;
    }
    df(1);
    for(i=0;i<n;i++)
        if(s[i]==0){
            df(s[i]);
            q++;
        }
    cout<<q;
    return 0;
}