Pagini recente » Cod sursa (job #3292784) | Cod sursa (job #2648346) | Cod sursa (job #2400824) | Cod sursa (job #1953549) | Cod sursa (job #305889)
Cod sursa(job #305889)
#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]])
{con++;viz(a[x][k]);}
culoare[x]=1;
}
void DFS()
{
for(i=1;i<=n;i++)
for(j=1;j<=a[i][0];j++)
if(!culoare[a[i][j]])
viz(a[i][j]);
}
int main()
{
citire();
DFS();
//viz(3);
o<<con;
return 0;}