Cod sursa(job #1331892)

Utilizator anaid96Nasue Diana anaid96 Data 1 februarie 2015 12:25:35
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include<stdio.h>
#include<vector>
#include<stack>
#include<utility>
#include<algorithm>
#include<set>

using namespace std;

FILE *in, *out;

//definitions
#define pb push_back
#define mp make_pair
#define pii pair<int,int>

//constants
const int Nmax = (int)1e5+1;

//variables
int nodes, edges;
int node1, node2;
int dfn[Nmax], low[Nmax];
int num;


vector<int> graph[Nmax];
vector<set<int> > answer;

stack<pii> sol;

//functions
void dfs(int node, int father);
void biconex( pii stop);

int main(void)
{
	in = fopen("biconex.in", "rt");
	out = fopen("biconex.out", "wt");
	
	fscanf(in, "%d%d", &nodes, &edges);
	
	while(edges--)
	{
		fscanf(in, "%d%d", &node1, &node2);
		graph[node1].pb(node2);
		graph[node2].pb(node1);
	}
	
	for(int i=1; i<=nodes; ++i)
		dfn[i] = low[i] = -1;
	
	dfs(3,-1);
	
	fprintf(out, "%d\n", answer.size());
	
	vector<set<int> > :: iterator it, end=answer.end();
	
	for(it=answer.begin(); it!=end; ++it)
	{
		set<int> :: iterator sit, send=it->end();
		for(sit=it->begin(); sit!=send; ++sit)
			fprintf(out,"%d ",*sit);
		fprintf(out,"\n");
	}
	fclose(in);
	fclose(out);
	return 0;
}

void dfs(int node, int father)
{
	dfn[node] = low[node] = ++num;
	
	vector<int> :: iterator it, end=graph[node].end();
	
	for( it=graph[node].begin(); it!=end; ++it)
	{
		if(*it != father && dfn[*it] < dfn[node])
			sol.push(mp(node,*it));
		
		if(dfn[*it] == -1)
		{
			dfs(*it, node);
			
			low[node] = min(low[node], low[*it]);
			if(low[*it] >= dfn[node])
				biconex(mp(node,*it));
		}	
		else
		{
			if(*it!=father)
				low[node] = min(low[node], dfn[*it]);
		}
	}
	
}

void biconex(pii stop)
{
	set<int> temp;
	
	pii curent;
	
	do
	{
		curent = sol.top();
		sol.pop();
		
		temp.insert(curent.first);
		temp.insert(curent.second);
		
	}
	while(curent!=stop);
	
	answer.pb(temp);
	
	temp.clear();
}