Cod sursa(job #2311901)

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

using namespace std;
FILE *fin, *fout;

int start[100002],t[2][400002];
bool viz[100002];
deque <int>flu;
void ddfs(int nod)
{
    flu.push_back(nod);
    viz[nod]=1;
    while(!flu.empty()){
        nod=flu.front();
        flu.pop_front();
        int p;
        p=start[nod];
        while(p){
            if(viz[t[0][p]]==0)
                viz[t[0][p]]=1,flu.push_back(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;
}