Cod sursa(job #1621748)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 29 februarie 2016 21:15:56
Problema Componente biconexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <bitset>
#include <vector>
#include <queue>
#include <set>

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

int low[100010], niv[100010], N, M, x, y, nr;
pair<int ,int> a;

vector<int>L[100010];
set<int> SOL[200100];
set<int>::iterator it;
bitset<100010>v, X;
deque<pair<int, int> >Q;

void dfs(int node, int nivel, int tata)
{
    v[node] = 1;
    Q.push_back(make_pair(tata, node));
    low[node] = niv[node] = nivel;

    for(int i = 0; i < L[node].size(); i ++)
    {
        if(L[node][i] == tata)
            continue;

        if(v[ L[node][i] ] == 0)
        {
            dfs(L[node][i], nivel + 1, node);
            low[node] = min(low[node], low[ L[node][i] ]);

            if(low[ L[node][i] ] >= niv[node])
            {
                nr ++;
                do{
                    a = Q.back();
                    SOL[nr].insert(a.first);
                    SOL[nr].insert(a.second);
                    Q.pop_back();
                }while(a.first != node && a.second != L[node][i]);
            }
        }
        else
        {
            low[node] = min(low[node], low[ L[node][i] ]);
        }
    }
}

int main()
{
    fin >> N >> M;

    for(int i = 1; i <= M; i ++)
    {
        fin >> x >> y;
        L[x].push_back(y);
    }

    dfs(1, 1, 0);

    fout << nr << '\n';

    for(int i = 1; i <= nr; i ++)
    {
        for(it = SOL[i].begin(); it != SOL[i].end(); it ++)
        {
            fout << *it << " ";
        }

        fout << '\n';
    }

    return 0;
}