Cod sursa(job #1737772)

Utilizator Bulgaru_Robert_Razvan_323CBBulgaru Robert Razvan Bulgaru_Robert_Razvan_323CB Data 4 august 2016 19:20:37
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <cstring>
#include <stack>
#include <vector>

using namespace std;

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

unsigned int n,m,x,y,node,indx,nrComp=0;

int idx[100005];
int lowLink[100005];
int inStack[100005];

vector<int> graph[100005];
stack<int> st;

unsigned int min(unsigned int a,unsigned int b) {
	if (a>=b)
		return b;
	return a;
}

void tarjan(unsigned int v) {
	idx[v]=indx;
	lowLink[v]=indx;
	indx++;

	st.push(v);
	inStack[v]=1;

	for (unsigned int u=0;u<graph[v].size();u++) {
		if (idx[graph[v][u]]==-1) {
			tarjan(graph[v][u]);
			lowLink[v]=min(lowLink[v],lowLink[graph[v][u]]);
		}
		else if (inStack[graph[v][u]])
			lowLink[v]=min(lowLink[v],idx[graph[v][u]]);
	}

	if (idx[v]==lowLink[v]) {
		nrComp++;
	}
}

void ctcTarjan() {
	indx=0;

	for (unsigned int i=1;i<=n;i++) 
		if (idx[i]==-1)
			tarjan(i);
}

int main() {
	memset(idx,-1,sizeof(idx));
	memset(lowLink,0,sizeof(lowLink));
	memset(inStack,0,sizeof(inStack));

	in>>n>>m;

	for (unsigned int i=0;i<m;i++) {
		in>>x>>y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}

	ctcTarjan();

	out<<nrComp;

	return 0;
}