Cod sursa(job #1241977)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 13 octombrie 2014 21:07:06
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <cstdio>
#include <vector>
#define nmv 100010
#include <stack>

using namespace std;

vector < long > gr[nmv];
stack < long > st;
bool td[nmv];
long n,m;
long sum;

void read(){
  scanf("%ld %ld ",&n,&m);
  long x,y;
  while(m--){
    scanf("%ld %ld ",&x,&y);
    gr[x].push_back(y);
    gr[y].push_back(x);
  }
}

void dfs(long v){
    st.push(v);
    long i;
    while(!st.empty()){
        i=st.top();
        st.pop();
        if(!td[i]){
            td[i]=1;
            for(vector < long > :: iterator it=gr[i].begin();it!=gr[i].end();++it)
                st.push(*it);
        }
    }
}

void solve(){
   long i=1;
   do{
     dfs(i);
     sum++;
     while(i<=n && td[i])i++;
   }while(i<=n);
}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    read();
    solve();
    printf("%ld\n",sum);
    return 0;
}