Cod sursa(job #2186767)

Utilizator rrobertBulgaru Robert rrobert Data 25 martie 2018 22:01:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

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

bool in_stack[100005];

int low[100005];
int idx[100005];
int n,m,x,y,index,nr=0;

int min(int a,int b) {
	return a<b?a:b;
}

void tarjan(int u) {
	idx[u]=index;
	low[u]=index;
	index=index+1;

	s.push(u);
	in_stack[u]=true;

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

	if (low[u]==idx[u])
		nr++;

}

void ctc_tarjan() {
	index=0;

	for (int i=1;i<=n;i++) {
		in_stack[i]=false;
		low[i]=0;
		idx[i]=-1;
	}

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

int main() {
	in>>n>>m;

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

	ctc_tarjan();

	out<<nr<<endl;
	in.close();
	out.close();
	return 0;
}