Cod sursa(job #957880)

Utilizator smaraldaSmaranda Dinu smaralda Data 6 iunie 2013 12:01:46
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.38 kb
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#include<cstring>
#define NMAX 100000
#define MMAX 200000
using namespace std;
struct EDGE { int ind, v; };
vector <EDGE> graph[NMAX+10];
vector <int> biconex[NMAX+10];
const int kinf=2e9;
int nr,N,M,lvl,dp[NMAX+10],level[NMAX+10],dad[NMAX+10];
bool bad[MMAX+10];
int viz[NMAX+10];
EDGE m_edge (int a, int b)
{
    EDGE aux;
    aux.ind=a;
    aux.v=b;
    return aux;
}

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])
            {
                dad[graph[x][i].v]=x;
                dfs(graph[x][i].v,graph[x][i].ind);
                dp[x]=min(dp[x],dp[graph[x][i].v]);
            }
        else
            if(graph[x][i].v!=dad[x])
                dp[x]=min(dp[x],level[graph[x][i].v]);
    if(dp[x]>=level[x])
        bad[e]=1;
    --lvl;
}
vector < pair<int,int> > o;
void alt_dfs (int x)
{
    int i;
    viz[x]=nr;
    for(i=0;i<graph[x].size();i++)
        if(!bad[graph[x][i].ind] && !viz[graph[x][i].v])
            alt_dfs(graph[x][i].v);
        else
            if(bad[graph[x][i].ind] && !viz[graph[x][i].v])
                o.push_back(make_pair(graph[x][i].v,x));
}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    int x,i,y,j,num;
    scanf("%d%d",&N,&M);
    for(i=1;i<=M;i++)
        {
            scanf("%d%d",&x,&y);
            graph[x].push_back(m_edge(i,y));
            graph[y].push_back(m_edge(i,x));
        }
    lvl=0;
    for(i=1;i<=N;i++)
        if(!viz[i])
            dfs(i,0);
    memset(viz,0,sizeof(viz));
    nr=0;
    for(i=1;i<=N;i++)
        if(!viz[i])
            {
                nr++;
                alt_dfs(i);
            }
    for(i=1;i<=N;i++)
        biconex[viz[i]].push_back(i);


    for(i=0;i<o.size();i++)
        biconex[++nr].push_back(o[i].first),
        biconex[nr].push_back(o[i].second);

    num=0;
    for(i=1;i<=nr;i++)
        if(biconex[i].size()>1)
            num++;

    printf("%d\n",num);
    for(i=1;i<=nr;i++)
        if(biconex[i].size()>1)
            {
                for(j=0;j<biconex[i].size();j++)
                    printf("%d ",biconex[i][j]);
                printf("\n");
            }

    return 0;
}