Pagini recente » Cod sursa (job #1968191) | Cod sursa (job #1109282) | Cod sursa (job #2727537) | Cod sursa (job #1088881) | Cod sursa (job #1889954)
///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;
}