Cod sursa(job #457308)

Utilizator mlupseLupse-Turpan Mircea mlupse Data 18 mai 2010 21:03:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
using namespace std;
#include <fstream>
ifstream fin("dfs.in");
ofstream fout("dfs.out");

int n, m, s[100005], nr;
 
struct nod
{
    int inf;
    nod *urm;
} * v[100005];
 
void add(nod *&prim, int val)
{
    nod * p;
    p = new nod;
    p -> inf = val;
    p -> urm = prim;
    prim = p;
}
 
void citire()
{
    fin>>n>>m;
    int i, x, y;
 
    for (i = 1; i <= m; i++)
    {
        fin>>x>>y;
        add(v[x], y);
        add(v[y], x);
    }
}
 
void dfs(int x)
{
    nod * p;
    s[x] = 1;
    for (p = v[x]; p != NULL; p = p -> urm) if (!s[p -> inf]) dfs(p -> inf);
}  
 
int main()
{
    citire();
    for (int i = 1; i <= n; i++) 
		if (!s[i]) 
		  { dfs(i);nr++;}
    fout<<nr<<"\n";
    return 0;
}