Cod sursa(job #1731689)

Utilizator mariakKapros Maria mariak Data 19 iulie 2016 16:01:51
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.2 kb
#include <bits/stdc++.h>
#define Nmax 100002
#define pii pair<int, int>
#define pb(x) push_back(x)
FILE *fin  = freopen("biconex.in", "r", stdin);
FILE *fout = freopen("biconex.out", "w", stdout);

using namespace std;
int N, M, low[Nmax], disc[Nmax], Time, parent[Nmax];
vector <int> G[Nmax];
stack<pii> St;
vector <int> aux;
vector< vector< int > > sol;
void read()
{
    int x, y;
    scanf("%d %d", &N, &M);
    while(M --)
    {
        scanf("%d %d", &x, &y);
        G[x].pb(y);
        G[y].pb(x);
    }
}
int Min(int x, int y)
{
    return x < y ? x : y;
}
void Form_BCC(pair <int, int> p)
{
    pair <int, int> x;
    do
    {
        x = St.top();
        St.pop();
        aux.pb(x.first);
        aux.pb(x.second);
    }
    while(x != p);

    sort(aux.begin(), aux.end());
    aux.erase(unique(aux.begin(), aux.end()), aux.end());
    sol.pb(aux);
    aux.clear();
}
void BCC(int u)
{
    /// // Initialize discovery time and low value
    disc[u] = low[u] = ++ Time;

    /// Go through all vertices adjacent to this
    vector<int> :: iterator i;
    for (i = G[u].begin(); i != G[u].end(); ++ i)
    {
        int v = *i;
        /// If v is not visited the recur for it
        if(!disc[v]) /// tree edge
        {
            St.push(make_pair(u, v));
            parent[v] = u;
            BCC(v);
            low[u] = Min(low[u], low[v]);

            ///If u is an articulation point,
            ///pop all edges from stack till u -- v
            if(low[v] >= disc[u]) /// v - articulation point
                Form_BCC(make_pair(u, v));
        }
        else if(v != parent[u] && disc[v] < low[u]) /// back edge
        {
            St.push(make_pair(u, v));
            low[u] = Min(low[u], disc[v]);
        }
    }
}
void solve()
{
    for(int i = 1; i <= N; ++ i)
        if(!disc[i]) BCC(i);
}
void write()
{
    int sz = sol.size();
    printf("%d\n", sz);
    for(int i = 0; i < sz; i++)
    {
        int szp = sol[i].size();
        for(int j = 0; j < szp; ++ j)
        {
            printf("%d ", sol[i][j]);
        }
        printf("\n");
    }
}
int main()
{
    read();
    solve();
    write();
    return 0;
}