Pagini recente » Cod sursa (job #1920936) | Cod sursa (job #31120) | Cod sursa (job #2982021) | Cod sursa (job #1932600) | Cod sursa (job #2401428)
#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;
}