Pagini recente » Cod sursa (job #1074175) | Cod sursa (job #650640) | Cod sursa (job #1112231) | Cod sursa (job #1376612) | Cod sursa (job #1274154)
#include<fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
struct Node
{
int data;
Node *next;
}*V[100001];
int viz[100001],N,M,nr;
void add_to_list(int nr,int data)
{
Node *p=new Node;
p->data=data;
p->next=V[nr];
V[nr]=p;
}
void remove_first(int nr)
{
if(V[nr])
{
Node *p=V[nr];
V[nr]=p->next;
delete p;
}
}
void DFS(int t)
{
viz[t]=1;
while(V[t])
{
if(!viz[V[t]->data])
DFS(V[t]->data);
remove_first(t);
}
}
int main()
{
in>>N;
in>>M;
int j,k;
for(int i=1;i<=M;i++)
{
in>>j>>k;
add_to_list(j,k);
add_to_list(k,j);
}
for(int i=1;i<=N;i++)
{
if(!viz[i])
{
DFS(i);
nr++;
}
}
out<<nr;
in.close();
out.close();
return 0;
}