Cod sursa(job #2163887)

Utilizator TooHappyMarchitan Teodor TooHappy Data 12 martie 2018 20:22:12
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>
using namespace std;
 
ifstream in("dfs.in");
ofstream out("dfs.out");

const int NMax = 1e5 + 5;
vector< vector< int > > G(NMax);
vector< bool > viz(NMax);
vector< int > componenteConexe(NMax);

void DFS(int nod, int componentaActuala) {
	viz[nod] = true;
	componenteConexe[nod] = componentaActuala;

	for(auto vecin: G[nod]) {
		if(!viz[vecin]) {
			DFS(vecin, componentaActuala);
		}
	}
}

int main() {

	int n, m; in >> n >> m;

	for(int i = 1; i <= m; ++i) {
		int x, y; in >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}

	int componentaActuala = 0;
	for(int i = 1; i <= n; ++i) {
		if(!viz[i]) {
			DFS(i, ++componentaActuala);
		}
	}

	out << *max_element(componenteConexe.begin(), componenteConexe.end());

    in.close(); out.close();
 
    return 0;
}