Pagini recente » Cod sursa (job #696598) | Cod sursa (job #457946) | Istoria paginii preoni-2005/runda-1/clasament-11-12 | Politia | Cod sursa (job #305891)
Cod sursa(job #305891)
#include<iostream>
#include<fstream>
#define IMAX 200000
//condition ? value if true : value if false
using namespace std;
ifstream f ("dfs.in");
ofstream o ("dfs.out");
int n,m,i,j, *a[IMAX],culoare[IMAX];
//int drum[IMAX];
void citire()
{
f>>n>>m;
int x,y;
for(i=1;i<=n;i++)
{
a[i]=(int *)realloc(a[i],sizeof(int));
a[i][0]=0;
}
for(i=1;i<=m;i++)
{
f>>x>>y;
a[x][0]++;
a[x]=(int *)realloc(a[x],(a[x][0]+1)*sizeof(int));
a[x][a[x][0]]=y;
a[y][0]++;
a[y]=(int *)realloc(a[y],(a[y][0]+1)*sizeof(int));
a[y][a[y][0]]=x;
}
}
int con;
void viz(int x)
{
culoare[x]=2;
int k;
for(k=1;k<=a[x][0];k++)
if(!culoare[a[x][k]])
viz(a[x][k]);
}
void DFS()
{
for(i=1;i<=n;i++)
if(!culoare[i])
{con++; viz(i);}
}
int main()
{
citire();
DFS();
//viz(3);
o<<con;
return 0;}