Cod sursa(job #743964)

Utilizator memaxMaxim Smith memax Data 6 mai 2012 21:27:41
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#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;
     }