Cod sursa(job #957883)

Utilizator thewildnathNathan Wildenberg thewildnath Data 6 iunie 2013 12:13:51
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;

struct edge
{
    int v,e;

    edge(int x1, int y1){
        v = x1;
        e = y1;
    }
};

vector <edge> graph[100002];

const int kinf=2e9;
int viz[100002],lvl,dp[100002],t[100002],level[100002],bad[200002];
vector <vector<int> > ans;
vector <int> st;

void dfs2(int x)
{
    int i;
    st.push_back(x);
    viz[x]=1;
    for(i=0;i<graph[x].size();i++)
        if(!viz[graph[x][i].v]&&!bad[graph[x][i].e])
            dfs2(graph[x][i].v);
        else
            if(!viz[graph[x][i].v]&&bad[graph[x][i].e])
            {
                vector <int> a;
                a.push_back(x);
                a.push_back(graph[x][i].v);
                ans.push_back(a);
            }
}

void dfs(int x,int e)
{
    int i;
    viz[x]=1;
    ++lvl;
    level[x]=lvl;
    dp[x]=kinf;
    for(i=0;i<graph[x].size();++i)
    {
        if(!viz[graph[x][i].v])
        {
            t[graph[x][i].v] = x;
            dfs(graph[x][i].v,graph[x][i].e);
            dp[x]=min(dp[x],dp[graph[x][i].v]);
        }
        else if(graph[x][i].v!=t[x])
            dp[x]=min(dp[x],level[graph[x][i].v]);
    }
    if(dp[x]>=level[x])
        bad[e]=1;
    --lvl;
}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    int n,m,i,x,y;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        graph[x].push_back(edge(y,i));
        graph[y].push_back(edge(x,i));
    }
    for(i=1;i<=n;i++)
        if(!viz[i])
            dfs(i,0);
    memset(viz,0,sizeof(viz));

    for(i=1;i<=n;i++)
        if(!viz[i])
        {
            st.clear();
            dfs2(i);
            if(st.size()>1)
                ans.push_back(st);
        }

    printf("%d\n",ans.size());
    for(i=0;i<ans.size();i++)
    {
        for(int j=0;j<ans[i].size();j++)
            printf("%d ",ans[i][j]);
        printf("\n");
    }
    return 0;
}