Cod sursa(job #1909136)

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

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

int N, M, cnt, maxi;
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;
    //cout << u << " ";
    for(int i=0; i<adj[u].size(); i++) {
        if(visited[adj[u][i]] == 0) {
            cnt++;
            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 = 1;
            DFS(i, adj);
            if(cnt > maxi) maxi = cnt;
        }
    }
    cout << maxi;
    return 0;
}