Mai intai trebuie sa te autentifici.
Cod sursa(job #1123856)
Utilizator | Data | 26 februarie 2014 10:25:56 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 5 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1 kb |
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int N, M, rez = 0;;
vector<vector<int> > V;
vector<int> VIZ;
void solve()
{
for(int i=1;i<=N;++i)
{
if(!VIZ[i])
{
for(vector<int>::iterator it=V[i].begin();it!=V[i].end();++it)
VIZ[*it] = 1;
++rez;
}
}
}
int main()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%d %d", &N, &M);
for(int i=0;i<=N;++i)
{
V.push_back(vector<int>());
VIZ.push_back(0);
}
for(int i=1;i<=M;++i)
{
int X, Y;
scanf("%d %d", &X, &Y);
V[X].push_back(Y);
}
solve();
/*
for(vector<vector<int> >::iterator it=V.begin();it!=V.end();++it)
{
for(vector<int>::iterator it2=(*it).begin();it2!=(*it).end();++it2)
cout<<*it2<<" ";
cout<<"\n";
}*/
cout<<rez<<"\n";
return 0;
}