Cod sursa(job #1188293)

Utilizator corina.ioanaSerbanescu Corina corina.ioana Data 19 mai 2014 11:32:59
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include <cstdio>

using namespace std;
int i,j,m,n,x,y,a[1000][1000],nr;
bool ok[1000000];
void dfs(int x)
{
    int i;
    ok[x]=true;
    for(i=1; i<=n; i++)
    {
        if(a[x][i]==1 && ok[i]==false) dfs(i);
    }
}
int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1; i<=m; i++)
    {
        scanf("%d %d",&x,&y);
        a[x][y]++;
        a[y][x]++;
    }
    for(i=1; i<=n; i++)
    {
        if(ok[i]==false) {dfs(i);nr++;}
    }
    printf("%d\n",nr);
    return 0;
}