Cod sursa(job #804797)

Utilizator zeeboBuzatu Vlad zeebo Data 30 octombrie 2012 14:59:23
Problema Parcurgere DFS - componente conexe Scor 65
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <string.h>
using namespace std;
struct point
{
    int inf;
    point *leg;
};
point *l[100001],*p;
bool sel[100001];
int nr,n,m,x,y,i;
void dfs (int x)
{
    point *po;
    sel[x]=true;
    po=new point; po=l[x];
    while (po)
    {
        if (!sel[po->inf]) dfs(po->inf);
        po=po->leg;
    }
}
int main()
{
   ifstream f("dfs.in");
   ofstream g("dfs.out");
   f>>n>>m;
   memset(l,NULL,sizeof(l));
   for (i=1;i<=n;i++)
   {
       f>>x>>y;
       p=new point;
       p->inf=y;
       p->leg=l[x];
       l[x]=p;
       p=new point;
       p->inf=x;
       p->leg=l[y];
       l[y]=p;
   }
for (i=1;i<=n;i++)
 if (!sel[i]) dfs(i),nr++;
 g<<nr<<'\n';
 return 0;
}