Pagini recente » Cod sursa (job #1045494) | Cod sursa (job #1254587) | Cod sursa (job #2213674) | Cod sursa (job #1056381) | Cod sursa (job #743964)
Cod sursa(job #743964)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
int m,n,a,b,t=0,q=0;
vector< vector<int> > g(1);
vector<int> d(1), f(1), c(1), p(1);
void de(int k);
int main(){
ifstream inr ("dfs.in");
ofstream our ("dfs.out");
inr >> n;
inr >> m;
for(int i=1; i<=n; i++){ g.push_back(vector<int> ());
c.push_back(0); p.push_back(0);
f.push_back(-1); d.push_back(-1); }
for(int i=1; i<=m; i++){
inr >> a;
inr >> b;
g[b].push_back(a);
g[a].push_back(b);
}
for(int i=1; i<=n; i++){
if(c[i]==0){
q++;
de(i);
}
}
//for(int i=1; i<=n; i++){ cout << p[i] <<" "<<d[i]<<" "<< f[i]<<"\n"; }
our << q;
return 0;
}
void de(int k){
t++;
c[k]=1;
d[k]=t;
for(int i=0; i<g[k].size(); i++){
if(c[g[k][i]]==0){
p[g[k][i]]=k;
de(g[k][i]);
}
}
c[k]=2;
t++;
f[k]=t;
}