Cod sursa(job #957878)

Utilizator dariusdariusMarian Darius dariusdarius Data 6 iunie 2013 11:52:05
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
vector< pair<int,int> > G[100005];
const int INF=1000000000;
struct EDGE {int x,y;} edge[200005];
int edge_to_dad[100005];
bool critic[200005];
bool viz[100005];
vector<int> sol;
vector< vector<int> > cc;
int level[100005];
int dp[100005];
int  t[100005];
int lvl,n,m;
int nr_critics;
void dfs(int u)
{
    viz[u]=true;
    level[u]=lvl++;
    dp[u]=INF;
    for(vector< pair<int,int> >::iterator it=G[u].begin();it!=G[u].end();it++)
        if(!viz[it->first])
        {
            t[it->first]=u;edge_to_dad[it->first]=it->second;
            dfs(it->first);
            dp[u]=min(dp[u],dp[it->first]);
        }
        else if(it->first!=t[u])
            dp[u]=min(dp[u],level[it->first]);
    if(dp[u]>=level[u])
	{
        critic[edge_to_dad[u]]=true;
		nr_critics++;
    }
	lvl--;
}
void dfs2(int u)
{
	viz[u]=true;
	sol.push_back(u);
	for(vector< pair<int,int> >::iterator it=G[u].begin();it!=G[u].end();it++)
		if(!viz[it->first] && !critic[it->second])
			dfs2(it->first);
}
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&edge[i].x,&edge[i].y),
        G[edge[i].x].push_back(make_pair(edge[i].y,i)),
        G[edge[i].y].push_back(make_pair(edge[i].x,i));
    for(int i=1;i<=n;i++)
        if(!viz[i])
            dfs(i),
			--nr_critics;
	memset(viz,0,sizeof viz);
	for(int i=1;i<=n;i++)
		if(!viz[i])
		{
			sol.clear();
			dfs2(i);
			if((int)sol.size()>1)
				cc.push_back(sol);
		}
	printf("%d\n",nr_critics+(int)cc.size());
	for(int i=0;i<(int)cc.size();i++)
		for(int j=0;j<(int)cc[i].size();j++)
			printf("%d%c",cc[i][j],j==(int)cc[i].size()-1?'\n':' ');
	for(int i=1;i<=m;i++)
		if(critic[i])
			printf("%d %d\n",edge[i].x,edge[i].y);
    return 0;
}