Pagini recente » Cod sursa (job #772595) | Cod sursa (job #1210740) | Cod sursa (job #1683344) | Cod sursa (job #63845) | Cod sursa (job #2007206)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int N, M;
bool a[1001][1001], viz[1001];
//DFS adancime
void citiregraf()
{
f >> N >> M;
while(M--)
{
int x, y;
f >> x >> y;
a[x][y] = a[y][x] = 1;
}
}
/*
void afisareMatAdiacenta()
{
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= N; j++)
cout << a[i][j] << ' ';
cout << endl;
}
cout << endl;
}
*/
void adancime(int x)
{
int j, vf, cr, s[1001];
vf = 1;
s[vf] = x;
viz[x] = 1;
//cout << x << ' ';
while(vf != 0)
{
cr = s[vf];
int gasit = 0;
for(j = 1; j <= N; j++)
if(a[cr][j] == 1 && viz[j] == 0)
{
gasit = 1;
break;
}
if(gasit)
{
//cout << j << ' ';
s[++vf] = j;
viz[j] = 1;
}
else vf--;
}
//cout << endl;
}
void componente()
{
int i, compconex = 0;
for(i = 1; i <= N; i++)
viz[i] = 0;
for(i = 1; i <= N; i++)
if(viz[i] == 0)
{
adancime(i);
compconex++;
}
g << compconex;
}
int main()
{
citiregraf();
//afisareMatAdiacenta();
componente();
return 0;
}