Cod sursa(job #798738)

Utilizator bulbulicaAlexandrescu Cristian bulbulica Data 17 octombrie 2012 08:05:19
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");

int n, m, viz[100005], cnt;

struct nod
{
    int inf;
    nod *adr;
} *v[100005];

void citire()
{
	f>>n>>m;
	int i, x, y;
	for (i = 1; i <= m; i++)
	{
		f>>x>>y;
		nod *p = new nod;
		p -> inf = y;
		p -> adr = v[x];
		v[x]=p;
		p = new nod;
		p -> inf = x;
		p -> adr = v[x];
		v[y]=p;
    }
}
void DFS(int x)
{
    viz[x]=1;
    for (nod *p = v[x]; p != NULL; p = p -> adr) if (!viz[p -> inf]) DFS(p -> inf);
}
int main()
{
    citire();
    int i;
    for (i = 1; i <= n; i++) if (!viz[i]) { cnt++; DFS(i);}
    g<<cnt;
    return 0;
}