Cod sursa(job #1629112)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 4 martie 2016 12:48:40
Problema Componente biconexe Scor 94
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <iomanip>
#define MOD 9917
#define NMAX 100005
#define INF 0x3f3f3f3f
#define pb push_back

using namespace std;

FILE *fin = freopen("biconex.in", "r", stdin);
FILE *fout = freopen("biconex.out", "w", stdout);

typedef pair<int, int> pii;

vector<int> v[NMAX];
int dfn[NMAX], low[NMAX];
vector<vector<int> > C;
stack<pii> st;

void DFS(int x, int p, int nr);
void add_comp(int x, int y);

int main() {
    int n, i, x, y, a, b, sum=0,m,j;

    cin>>n>>m;

    for(i=0;i<m;++i) {
        cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }

    memset(dfn, -1, sizeof(dfn));
    DFS(1,0,0);

    cout<<C.size()<<'\n';
    for(i=0;i<C.size();++i) {
        sort(C[i].begin(), C[i].end());

        for(j=0;j<C[i].size();++j)
            if(C[i][j] != C[i][j-1])
                cout<<C[i][j]<<' ';
        cout<<'\n';
    }

    return 0;
}

void add_comp(int x, int y) {
    int x1,y1;
    vector<int> comp;
    do {
        x1=st.top().first;
        y1=st.top().second;
        st.pop();
        comp.pb(x1);
        comp.pb(y1);
    } while(x1!=x || y1!=y);

    C.pb(comp);
}

void DFS(int x, int p, int nr) {
    int i,y;

    dfn[x]=low[x]=nr;
    for(i=0;i<v[x].size();++i) {
        y=v[x][i];

        if(y == p)
            continue;
        if(dfn[y] == -1) {
            st.push({x, y});
            DFS(y,x,nr+1);
            low[x]=min(low[x], low[y]);

            if(low[y] >=dfn[x])
                add_comp(x, y);
        }
        else
            low[x]=min(low[x], dfn[y]);
    }
}