Cod sursa(job #2402553)

Utilizator oogaboogauvuvwevwevwe onyetenyevwe ugwemubwem ossas oogabooga Data 10 aprilie 2019 19:51:03
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 100005;

int N, M, anc[NMax], lvl[NMax], minlvl[NMax], nc;
bool vis[NMax];
vector <int> L[NMax], Comp[NMax];
stack < int > st;
inline bool comp(const vector <int> &, const vector <int> &);

void DFS_Tree(const int &node)
{
    vis[node] = 1;
    minlvl[node] = lvl[node];
    st.push(node);

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

        if(vis[next] == 0)
        {
            lvl[next] = lvl[node] + 1;
            anc[next] = node;

            DFS_Tree(next);

            minlvl[node] = min(minlvl[node], minlvl[next]);

            if(minlvl[next] >= lvl[node])
            {
                ++nc;
                while(!st.empty() && st.top() != next)
                {
                    Comp[nc].push_back(st.top());
                    st.pop();
                }
                Comp[nc].push_back(node);
                st.pop();
                Comp[nc].push_back(next);
            }
        }
        else
            if(next != anc[node] && minlvl[node] > lvl[next])
                minlvl[node] = lvl[next];
    }
}

int main()
{
    in>>N>>M;
    for(int i = 0; i < M; ++i)
    {
        int x, y;
        in>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }

    for(int i = 1; i <= N; ++i)
        if(vis[i] == 0)
        {
            lvl[i] = 1;
            DFS_Tree(i);
        }

    sort(Comp + 1, Comp + nc + 1);

    out<<nc<<"\n";

    for(int i = 1; i <= nc; ++i)
    {
        sort(Comp[i].begin(), Comp[i].end());

        for(int j = 0; j < Comp[i].size(); ++j)
            out<<Comp[i][j]<<" ";
        out<<"\n";
    }

    return 0;
}

inline bool comp(const vector <int> &A, const vector <int> &B)
{
    return A.size() < B.size();
}