Mai intai trebuie sa te autentifici.

Cod sursa(job #804798)

Utilizator ghegoiu1Ghegoiu Stefan ghegoiu1 Data 30 octombrie 2012 15:01:23
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <string.h>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
struct point {
    int inf;
    point *leg;
    };
point *G[100],*p;
int sel[1000];
void dfs(int x)
    {
        point *p;
        sel[x]=1;
        p=new point;
        p=G[x];
        while (p) {
            if (sel[p->inf]==0)
            {
                dfs(p->inf);
            }
            p=p->leg;
        }
    }
int main()
{
    int i,x,y,n,m,nr=0;
    f>>n>>m;
    memset(G,NULL,sizeof(G));
    for (i=1;i<=m;i++)
    {
        f>>x>>y;
        p=new point;
        p->inf=y;
        p->leg=G[x];
        G[x]=p;
        p=new point;
        p->inf=x;
        p->leg=G[y];
        G[y]=p;
    }
    for(i=1;i<=n;i++)
        if(sel[i]==0)
        {
            nr++;
            dfs(i);
        }
    g<<nr;
    return 0;
}