Pagini recente » Cod sursa (job #1884770) | Cod sursa (job #1939468) | Cod sursa (job #1596545) | Cod sursa (job #1469830) | Cod sursa (job #1889946)
///1.DFS-COMPONENTE CONEXE
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
vector <int> lv[100000];
vector <int>::iterator it;
queue <int> corn;
int viz[100000];
int main()
{
FILE *f=fopen("dfs.in","r");
FILE *g=fopen("dfs.out","w");
int i,n,m,x,y;
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++)
{ fscanf(f,"%d%d",&x,&y);
lv[x].push_back(y);
lv[y].push_back(x);
}
int cnx=0,nc,j;
for(int j=1;j<=n;j++)
{
if(viz[j]==0)
{ cnx++;
corn.push(j);
while(!corn.empty())
{
nc=corn.front();
corn.pop();
for(it=lv[nc].begin();it!=lv[nc].end();++it)
{
if(viz[*it]==0)
{
viz[*it]=1;
corn.push(*it);
}
}
}
}
}
fprintf(g,"%d",cnx);
return 0;
}