Cod sursa(job #1921810)

Utilizator livliviLivia Magureanu livlivi Data 10 martie 2017 14:40:52
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include<cstdio>
#include<vector>
#include<bitset>
#include<utility>
#include<stack>
#define N 100000
using namespace std;

vector<int> vecin[N+1];
bitset<N+1> viz;
int niv[N+1];

vector<int> comp[N+1];
vector<int> ans[N+1];
int k;

stack<pair<int,int> > stk;

int stra[N+1];

void dfs(int nod,int nivel=1){
    viz.set(nod);
    niv[nod]=nivel;
    stra[nod]=nivel-1;

    for(int i=0;i<vecin[nod].size();i++){
        int now=vecin[nod][i];

        if (viz[now]==true) stra[nod]=min(stra[nod],niv[now]);
        else {
            stk.push(make_pair(nod,now));
            dfs(now,nivel+1);
            stra[nod]=min(stra[nod],stra[now]);

            if (stra[now]>=nivel){
                k++;

                int x=0,y;
                while(!stk.empty() &&x!=nod){
                    x=stk.top().first;
                    y=stk.top().second;

                    if (comp[x].empty() ||comp[x][comp[x].size()-1]!=k) comp[x].push_back(k);
                    if (comp[y].empty() ||comp[y][comp[y].size()-1]!=k) comp[y].push_back(k);

                    stk.pop();
                }
            }
        }
    }
}

int main(){
    freopen ("biconex.in","r",stdin);
    freopen ("biconex.out","w",stdout);
    int n,m,i;

    scanf ("%d%d",&n,&m);

    for(i=1;i<=m;i++){
        int x,y;
        scanf ("%d%d",&x,&y);

        vecin[x].push_back(y);
        vecin[y].push_back(x);
    }

    dfs(1);

    printf ("%d\n",k);
    for(i=1;i<=n;i++)
        for(int j=0;j<comp[i].size();j++)
            ans[comp[i][j]].push_back(i);

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

    return 0;
}