Pagini recente » Cod sursa (job #390225) | Cod sursa (job #101655) | Cod sursa (job #248295) | Cod sursa (job #2039962) | Cod sursa (job #736110)
Cod sursa(job #736110)
#include<fstream>
#include<stdlib.h>
#define nmax 100003
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int *A[nmax];
int v[nmax];
int i, j, n, m, x ,y ;
void parcurge(int k)
{
int i;
v[k] = 1;
for(i = 1; i <= A[k][0] ;i++)
if(v[A[k][i]] == 0 )
parcurge(A[k][i]);
}
void read()
{
int Nr = 0;
fin >> n >>m;
for(i = 1; i <= n ;i++)
{
A[i] = (int *) realloc(A[i], sizeof(int));
A[i][0] = 0;
}
for(i = 1; i<=m ;i++)
{
fin >>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;
}
// for(i = 1; i <= n; i++)
// {
// for(j = 1; j <= A[i][0] ; j++)
// {
// fout<< A[i][j] <<" " ;
//
// }
// fout << '\n' ;
// }
for(i = 1; i <= n ;i++)
{
if(v[i]==0)
{
Nr++;
parcurge(i);
}
}
fout << Nr ;
}
int main()
{
read();
fin.close();
fout.close();
return 0;
}