Cod sursa(job #1621770)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 29 februarie 2016 21:34:58
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 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;
    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)
        {
            Q.push_back(make_pair(node, L[node][i]));
            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);
        L[y].push_back(x);
    }

    for(int i = 1; i <= N; i ++)
    {
        if(v[i] == 0)
        {
            dfs(i, 1, 0);
        }
    }

    fout << nr << '\n';

    for(int i = 1;i <= nr; i ++){
        while(!SOL[i].empty())
        {
            it = SOL[i].begin();
            fout << *it << " ";
            SOL[i].erase(it);
        }
    fout << '\n';
    }

    return 0;
}