Cod sursa(job #1122893)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 25 februarie 2014 21:09:27
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <map>
#include <set>


#define DN 100013
#define pb push_back
#define mp make_pair
#define per pair<int,int>
#define INF (1<<30)
#define LL long long
#define un unsigned
#define x first
#define y second
#define next_nod list[nod][i]
using namespace std;

vector<int> list[DN],rez[DN];
bitset<DN> viz,ap;
stack < per > st;
int t[DN],dp[DN],sz;

void solve(int nod,int nn){

    int tx,ty;
    vector<int> tmp;
    ap&=0;
    do{
        tx = st.top().x; ty = st.top().y;
        st.pop();
        if(!ap[tx])
            tmp.pb(tx);
        if(!ap[ty])
            tmp.pb(ty);
        ap[tx] = true;
        ap[ty] = true;
    }while(tx!=nod || ty!=nn);
    rez[++sz]=tmp;
}

void dfs(int nod,int niv){

    viz[nod]=true;
    dp[nod] = niv;
    for(un int i=0;i<list[nod].size();++i){

        if(!viz[next_nod]){

            st.push(mp(nod,next_nod));
            t[next_nod] = nod;
            dfs(next_nod,1+niv);

            if(dp[next_nod] >= niv)
                solve(nod,next_nod);

        }
        if( next_nod != t[nod])
            dp[nod]=min(dp[nod],dp[next_nod]);
    }

}

int main()
{
    int n,m;
    ifstream f("biconex.in");
    ofstream g("biconex.out");
    f>>n>>m;
    for(;m--;){

        int a,b;
        f>>a>>b;
        list[a].pb(b);
        list[b].pb(a);
    }
    dfs(1,1);
    g<<sz<<"\n";
    for(int i=1;i<=sz;++i,g<<"\n")
        for(un int j=0;j<rez[i].size();++j)
            g<<rez[i][j]<<" ";

    return 0;
}