Cod sursa(job #1667766)

Utilizator kasperDorin Puscasu kasper Data 29 martie 2016 10:52:11
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
 
using namespace std;

ifstream cin("dfs.in");
ofstream cout("dfs.out");
 
bool viz[100005];
int n, m, x, y, con;
 
typedef struct nod{
        int inf;
        nod* next;
} *lnod;

lnod A[1005];
 
void add(lnod &a, int x){
        lnod q = new nod;
        q->inf = x;
        q->next = a;
        a = q;
}
 
void dfs(int nd){
    viz[nd] = 1;
    for(lnod j = A[nd]; j; j = j->next ) 
		if(!viz[j -> inf]) 
			dfs(j->inf);
     
}
 
int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
	{
        cin >> x >> y;
        add(A[x],y);
        add(A[y],x);
    }
    for(int i = 1; i <= n; i++)
	{
        if(!viz[i])
		{ 
			dfs(i);
        	con++;
		}
    }
    cout << con;
    return 0;
}