Cod sursa(job #1581632)

Utilizator rebound212Mihnea Savu rebound212 Data 26 ianuarie 2016 22:57:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <cstdio>
#include <vector>
#define pb push_back
using namespace std;
bool sel[100001];
int n,m,x,y,nr;
vector <int> g[100001];
void dfs(int x)
{
 sel[x]=true;
  while(!g[x].empty())
  {
      if(sel[g[x].back()]==false)
      {
            dfs(g[x].back());
      }
      else
      {
          g[x].pop_back();
      }
  }
}
int main(){
     freopen("dfs.in","r",stdin);
     freopen("dfs.out","w",stdout);
     scanf("%d %d",&n,&m);
     int i;

     for(i=1;i<=m;i++)
     {
        scanf("%d %d",&x,&y);
        g[x].pb(y);
        g[y].pb(x);
     }
     for(i=1;i<=n;i++)
     {
       if(sel[i]==false) {nr++; dfs(i);}
     }
     printf("%d\n",nr);
    return 0;
}