Cod sursa(job #1713651)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 6 iunie 2016 08:42:25
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include<cstdio>
#include<vector>
#include<stack>
#define MAXN 100010
using namespace std;
vector<int> g[MAXN];
vector<int> component[MAXN];
stack<pair<int,int> > Stack;
int depth[MAXN],low[MAXN],seen[MAXN];
int components=0;
int minimum(int a,int b){
    if(a<b)
        return a;
    return b;
}
void CreateComponent(int node1,int node2){
    components++;
    int x=Stack.top().first,y=Stack.top().second;
    while(Stack.top().first!=node1&&Stack.top().second!=node2){
        component[components].push_back(Stack.top().second);
        Stack.pop();
    }
    component[components].push_back(node2);
    component[components].push_back(node1);
    Stack.pop();
}
void DFS(int node,int father){
    int i;
    depth[node]=low[node]=depth[father]+1;
    seen[node]=1;
    for(i=0;i<g[node].size();i++){
        if(seen[g[node][i]]==0){
            Stack.push(make_pair(node,g[node][i]));
            DFS(g[node][i],node);
            if(low[g[node][i]]>=depth[node])
                CreateComponent(node,g[node][i]);
        }
        if(g[node][i]!=father)
            low[node]=minimum(low[node],low[g[node][i]]);
    }
}
int main(){
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    int n,m,a,b,i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    DFS(1,0);
    printf("%d\n",components);
    for(i=1;i<=components;i++){
        for(j=0;j<component[i].size();j++)
            printf("%d ",component[i][j]);
        printf("\n");
    }
    return 0;
}