Cod sursa(job #2311897)

Utilizator Username01Name Surname Username01 Data 3 ianuarie 2019 20:17:50
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <cstdio>

using namespace std;
FILE *fin, *fout;

int start[100002],t[2][400002];
bool viz[100002];

void ddfs(int nod)
{
    int p;
    viz[nod]=1;
    p=start[nod];
    while(p)
    {
        if(viz[t[0][p]]==0) ddfs(t[0][p]);
        p=t[1][p];
    }
}
int main()
{
    int n,m,x,y,k=0;
    fin=fopen("dfs.in","r");
    fout=fopen("dfs.out","w");
    fscanf(fin,"%d %d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        fscanf(fin,"%d %d",&x,&y);
        t[0][++k]=y;
        t[1][k]=start[x];
        start[x]=k;

        t[0][++k]=x;
        t[1][k]=start[y];
        start[y]=k;
    }
    int da=0;
    for(int i=1;i<=n;++i)
        if(viz[i]==0) ++da,ddfs(i);
    fprintf(fout,"%d",da);

    return 0;
}