Pagini recente » Cod sursa (job #969170) | Cod sursa (job #921866)
Cod sursa(job #921866)
#include <iostream>
#include <fstream>
#include <stdio.h>
using namespace std;
#define MAX_N 100000
struct nod
{
int nr;
nod *next;
}*First[MAX_N+5];
int N,M;
int Visited[MAX_N+5];
void Insert(int x,int y)
{
nod *q=new nod;
q->nr=y;
q->next=First[x];
First[x]=q;
}
void Read()
{
ifstream fin("dfs.in");
fin>>N>>M;
int i,x,y;
for(i=1;i<=M;i++)
{
fin>>x>>y;
Insert(x,y);
Insert(y,x);
}
fin.close();
}
void DF(int k)
{
Visited[k]=1;
nod *q;
for(q=First[k];q;q=q->next)
{
if(Visited[q->nr]==0)
DF(q->nr);
}
}
int Resolve()
{
int i,s=0;
for(i=1;i<=N;i++)
{
if(Visited[i]==0)
{
DF(i);
s++;
}
}
return s;
}
int main()
{
Read();
ofstream fout("dfs.out");
fout<<Resolve();
fout.close();
return 0;
}