Cod sursa(job #2293861)

Utilizator andreiudilaUdila Andrei andreiudila Data 1 decembrie 2018 17:32:59
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <bits/stdc++.h>
#define pii pair<int,int>
#define fs first
#define sc second
#define pb push_back
#define zeros(x) x&(-x)
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define oo 2000000010
#define pii pair<int,int>
#define ll long long
#define ld long double
#define ull unsigned long long
#define mem(a) memset(a,0,sizeof(a))
#define pi 3.14159265359
using namespace std;
ifstream fin("a.in");
ofstream fout("a.out");

vector <int> v[100010],ans[100010];
int x,y,n,m,i,j,nrC;
stack <int> S;
int l[100010],d[100010];

void dfs(int node, int depth, int prev)
{
    d[node] = depth;
    l[node] = depth;
    S.push(node);

    for(auto next : v[node])
    {
        if(!d[next])
        {
            dfs(next, depth + 1, node);
            if(l[next] < d[node]) l[node] = min(l[node], l[next]);
            else
            {
                nrC++;

                int aux;
                do
                {
                    aux = S.top();
                    S.pop();
                    ans[nrC].push_back(aux);
                }
                while(aux != next);

                ans[nrC].push_back(node);
            }
        }

        else if(next != prev) l[node] = min(l[node], d[next]);
    }
}

int main()
{
    fin>>n>>m;
    for(i=1; i<=m; ++i)
    {
        fin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }

    dfs(1,1,0);

    fout << nrC << '\n';

    for(int i = 1; i <= nrC; i++)
    {
        for(int j = 0; j < ans[i].size(); j++)
        {
            fout << ans[i][j] << ' ';
        }

        fout << '\n';
    }


    return 0;
}