Cod sursa(job #1122875)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 25 februarie 2014 21:03:23
Problema Componente biconexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 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 dfs(int nod,int niv){

    viz[nod]=true;
    dp[nod] = niv;
    for(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] >= dp[nod]){

                vector<int> tmp;
                ap&=0;
                int tx,ty;
                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]=1;
                    ap[ty]=1;
                }while(tx!=nod || ty!=next_nod);
                rez[++sz]=tmp;
            }
        }
        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(int j=0;j<rez[i].size();++j)
            g<<rez[i][j]<<" ";

    return 0;
}