Cod sursa(job #1509348)

Utilizator timicsIoana Tamas timics Data 23 octombrie 2015 19:12:56
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
using namespace std;

int M,x,y;

int N,w[100100],low[100100],depth[100100],comp;
bool viz[100100];
vector<pair<int,int> > m;
vector <vector <int> > c;
vector <int> a[100100],com;

void dfs(int x, int p, int dep) {
    viz[x] = 1; depth[x]=dep; low[x]=dep;
    for(auto y: a[x]) {
        if(!viz[y]) {
            m.pb(mp(x,y)); dfs(y,x,dep+1);
            low[x] = min(low[x],low[y]);
            if(low[y] >= depth[x]) {
                ++comp; com.clear();
                while(true) {
                    int t = m.back().fs, u = m.back().sc;
                    if(w[t] != comp) {
                        w[t] = comp; com.pb(t);
                    }
                    if(w[u] != comp) {
                        w[u] = comp; com.pb(u);
                    }
                    m.pop_back();
                    if(t==x && u==y) break;
                }
                c.pb(com);
            }
        } else if(y!=p) {
            low[x]=min(low[x],depth[y]);
        }
    }
}

void biconex() {
    for(int i=1;i<=N;++i) {
        if(!viz[i]) {
            dfs(i,0,0);
        }
    }
}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;++i) {
        scanf("%d%d",&x,&y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    biconex();
    printf("%d\n",c.size());
    for(auto x: c) {
        for(auto y: x) {
            printf("%d ",y);
        }
        printf("\n");
    }
    return 0;
}