Cod sursa(job #1214586)

Utilizator cojocarugabiReality cojocarugabi Data 30 iulie 2014 20:57:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <vector>
using namespace std;
const int nmax=100000;
typedef struct nod{int x;nod *urm;} *pnod;
pnod a[nmax];
int s[nmax];
void dfs(int nod)
{
    s[nod]=1;
    pnod p;
    for (p=a[nod];p!=NULL;p=p->urm)
        if (!s[p->x])
           dfs(p->x);
}
int main(void)
{
   ifstream fi("dfs.in");
   ofstream fo("dfs.out");
   int n,m;
   fi>>n>>m;
   for (int i=1;i<=m;++i)
   {
       int x,y;
       fi>>x>>y;
       pnod p;
       p=new nod;
       p->x=x;
       p->urm=a[y];
       a[y]=p;
       p=new nod;
       p->x=y;
       p->urm=a[x];
       a[x]=p;
   }
   int N=0;
   for (int i=1;i<=n;++i)
       if (!s[i])
         {
            ++N;
            dfs(i);
         }
   fo<<N<<"\n";
}