Cod sursa(job #1909175)

Utilizator MailatMailat Radu Mailat Data 7 martie 2017 11:50:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdtr1c++.h>
using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

int N, M, cnt;
int visited[100010];

void addEdge(vector <int> adj[], int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void DFS(int u, vector <int> adj[]) {
    visited[u] = 1;
    for(int i=0; i<adj[u].size(); i++) {
        if(visited[adj[u][i]] == 0) {
            DFS(adj[u][i], adj);
        }
    }
}

int main()
{
    int x, y;
    fin >> N >> M;
    vector <int> adj[N+1];
    for(int i=0; i < M; i++) {
        fin >> x >> y;
        addEdge(adj, x, y);
    }
    for(int i=1;i <= N; i++) {
        if(!visited[i]){
            cnt++;
            DFS(i, adj);
        }
    }
    fout << cnt;
    return 0;
}