Pagini recente » Cod sursa (job #255192) | Cod sursa (job #2492347) | Cod sursa (job #3178786) | Cod sursa (job #2488927) | Cod sursa (job #1059351)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
struct Drum
{
unsigned int x,y;
};
static int parcurs[100001];
static Drum a[200000];
int n,m;
void parcurgere (int nod)
{
deque <int> coada;
coada.push_back (nod);
parcurs[nod] = 1;
while (!coada.empty())
{
for (int i=0; i<m; i++)
{
if ((a[i].x == coada.front()) && (parcurs[a[i].y] == 0))
{
parcurs[a[i].y] = 1;
coada.push_back (a[i].y);
}
if ((a[i].y == coada.front()) && (parcurs[a[i].x] == 0))
{
parcurs[a[i].x] = 1;
coada.push_back (a[i].x);
}
}
coada.pop_front();
}
}
int main()
{
ifstream f("dfs.in");
ofstream g("dfs.out");
f >> n >> m;
for (int i=0;i<m;i++)
f >> a[i].x >> a[i].y;
for (int i=1; i<=n;i++)
parcurs[i] = 0;
int k=0;
for (int i=n;i>0;i--)
{
if (parcurs[i] == 0 ) { k++; parcurgere(i); }
}
g << k << endl;
return 0;
}