Cod sursa(job #1232317)

Utilizator rebound212Mihnea Savu rebound212 Data 22 septembrie 2014 17:52:03
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <cstdio>
#include <vector>
#define pb push_back
using namespace std;
bool sel[1000];
int n,m,x,y,nr;
vector <int> g[10000];
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;
}