Cod sursa(job #2401428)

Utilizator TeodorAxinteAxinte Teodor TeodorAxinte Data 9 aprilie 2019 18:26:10
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin;
ofstream fout;
void DFS(int);
const int N=200010;
void add_edge(int,int);
struct node
{
    int info;
    node *next;
};
bitset<N> used;
int n,m,x,y,nr_components;
node *ADJ_list[N];
int main()
{
     fin.open("dfs.in");  fout.open("dfs.out");
     fin>>n>>m;
     for(;m!=0;m--)
     {
         fin>>x>>y;
         add_edge(x,y);
         add_edge(y,x);
     }
//    for(int i=1;i<=n;i++)
//    {
//        node * DSP = ADJ_list[i];
//        while(DSP!=NULL)
//        {
//            fout<<DSP->info<<' ';
//            DSP=DSP->next;
//        }
//        fout<<'\n';
//    }
     for(int i=1;i<=n;i++)
        if(!used[i])
     {
         DFS(i);
         nr_components++;
     }
     fout<<nr_components;
    return 0;
}
void DFS(int commence)
{
    node * B = ADJ_list[commence];
    while(B!=NULL)
    {
        if(!used[B->info])
        {
            used[B->info]=1;
            DFS(B->info);
        }
        B=B->next;
    }
}
void add_edge(int x,int y)
{
    node * USE = new node;
    USE->info=x;
    USE-> next=ADJ_list[y];
    ADJ_list[y]=USE;
}