Cod sursa(job #1967058)

Utilizator tudi98Cozma Tudor tudi98 Data 15 aprilie 2017 20:46:03
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>
using namespace std;

#define REP(i,a) for (int i = 0; i < a; i++)
#define FOR(i,a,b) for (int i = a; i <= b; i++)
#define ROF(i,a,b) for (int i = a; i >= b; i--)
#define FOREACH(it,x) for (auto it: (x))
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)(x).size())

int n,m;
vector<int> G[100001];
bool seen[100001];
int lvl[100001],low[100001];
vector< vector<int> > COMP;
stack<int> S;

void dfs(int node,int parent)
{
    S.push(node);
    seen[node] = 1;
    low[node] = lvl[node];
    FOREACH(it,G[node]) if (it != parent) {
        if (!seen[it])
        {
            lvl[it] = lvl[node] + 1;
            dfs(it,node);
            low[node] = min(low[node],low[it]);
            if (low[it] >= lvl[node])
            {
                COMP.pb(vector<int>());
                int u = S.top();
                while (u != node) {
                    COMP.back().pb(u);
                    S.pop(); u = S.top();
                }
                COMP.back().pb(u);
            }
        }
        else low[node] = min(low[node],lvl[it]);
    }
}

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

    fin >> n >> m;
    while (m--) {
        int x,y; fin >> x >> y;
        G[x].pb(y); G[y].pb(x);
    }
    lvl[1] = 1;
    FOR(i,1,n) if (!seen[i]) dfs(i,-1);
    fout << SZ(COMP) << "\n";
    FOREACH(v,COMP) {
        FOREACH(it,v) fout << it << " ";
        fout << "\n";
    }
}