Cod sursa(job #1401928)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 26 martie 2015 11:00:09
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include<cstdio>
#include<vector>
int max2(int a,int b){
    if(a>b)
        return a;
    return b;
}
int min2(int a,int b){
    if(a<b)
        return a;
    return b;
}
using namespace std;
const int N=100000,M=200000;
class Edge{
    public:
        int v1,v2;
        Edge(){
        }
        Edge(int vv1,int vv2){
            v1=vv1;
            v2=vv2;
        }
        bool operator==(const Edge&e)const{
            return v1==e.v1&&v2==e.v2;
        }
};
vector<int>cb[N+1];
vector<int>g[N+1];
Edge st[M+1];
int father[N+1];
int d[N+1];
int up[N+1];
bool vis[N+1];
int n,m,l,k;
void dfs(int dad){
    up[dad]=2*N;
    vis[dad]=true;
    for(unsigned int i=0;i<g[dad].size();i++){
        int son=g[dad][i];
        if(!vis[son]){
            st[++l]=Edge(dad,son);
            father[son]=dad;
            d[son]=d[dad]+1;
            dfs(son);
            up[dad]=min2(up[dad],up[son]);
            if(up[son]>=d[dad]){
                k++;
                bool f=true;
                while(f&&l){
                    cb[k].push_back(st[l].v2);
                    if(st[l]==Edge(dad,son)){
                        cb[k].push_back(st[l].v1);
                        f=false;
                    }
                    l--;
                }
            }
        }
        else
            if(son!=father[dad])
                up[dad]=min2(up[dad],d[son]);
    }
}
int main(){
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1);
    printf("%d\n",k);
    for(int i=1;i<=k;i++){
        for(unsigned int j=0;j<cb[i].size();j++)
            printf("%d ",cb[i][j]);
        printf("\n");
    }
    return 0;
}