Pagini recente » Monitorul de evaluare | Istoria paginii runda/infinity-2022-7/clasament | Istoria paginii runda/iulian/clasament | Istoria paginii runda/test_78/clasament | Cod sursa (job #1006768)
#include <fstream>
#include <algorithm>
#include <queue>
#include <iostream>
#include <list>
#define NMAX 100005
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n, m, viz[NMAX], p,i,x,y,a[3][1000010],k,start[100010],j,conex;
queue <int> q;
void dfs(int nod) {
int p, y;
//fout<<nod<<" ";
viz[nod] = 1;
x=start[nod];
while(x!=0)
{
// fout<<a[0][x]<<" ";
if(viz[a[0][x]]==0)
{
//dfs(a[0][x]);
q.push(a[0][x]);
}
x=a[1][x];
}
while(! q.empty())
{
p = q.front();
//fout<<p<<" ";
q.pop();
if(viz[p]==0)
{
//fout<<p<<" ";
dfs(p);
}
}
/* while(x!=0)
{
// fout<<a[0][x]<<" ";
if(viz[a[0][x]] ==0)
{
dfs(a[0][x]);
}
x=a[1][x];
}*/
}
int main() {
fin >> n >> m;
k=0;
for (i = 1; i <= m; i++) {
fin >> x >> y;
k++;
a[0][k]=y;
a[1][k]=start[x];
start[x]=k;
k++;
a[0][k]=x;
a[1][k]=start[y];
start[y]=k;
}
for(i=1;i<=n;i++)
{
if(viz[i]==0)
{
dfs(i);
conex++;
//fout<<"\n";
}
}
/*x=start[1];
while(x!=0)
{
fout<<a[0][x]<<" ";
x=a[1][x];
}*/
fout<<conex;
}