Mai intai trebuie sa te autentifici.
Cod sursa(job #1703092)
Utilizator | Data | 16 mai 2016 10:37:41 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.71 kb |
#include<iostream>
#include<fstream>
using namespace::std;
int m, n, k, viz[100005];
ifstream f("dfs.in");
ofstream g("dfs.out");
typedef struct nod
{
int info;
nod *next;
} *pN;
pN a[100005];
void add(pN &dest, int val)
{
pN q;
q = new nod;
q->info = val;
q->next = dest;
dest = q;
}
void citire()
{
int i, x, y;
f >> n >> m;
for (i = 1; i <= m; i++)
{
f >> x >> y;
add(a[x], y);
add(a[y], x);
}
}
void Dfs(int nod)
{
pN p;
viz[nod] = 1;
for (p = a[nod];p!=NULL;p=p->next)
if (!viz[p->info])
Dfs(p->info);
}
int main()
{
int i;
citire();
for (i = 1; i <= n;i++)
if (viz[i] == 0)
{
k++;
Dfs(i);
}
g<< k;
}