Cod sursa(job #2163968)

Utilizator andru47Stefanescu Andru andru47 Data 12 martie 2018 20:47:02
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>
using namespace std;
int n , m, level[100005], low[100005], lvl;
stack <pair <int , int> > stackk;
vector <int> g[100005];
vector <vector <pair <int , int> > > graphs;
inline void add_graph(pair <int , int> muchie)
{
    vector <pair <int , int> > vv;
    vv.clear();
    while (stackk.size() && stackk.top() != muchie)
    {
        vv.push_back(stackk.top());
        stackk.pop();
    }
    stackk.pop();
    vv.push_back(muchie);
    vv.push_back({1000 , muchie.first});
    graphs.push_back(vv);
    return ;
}
inline void dfs(int node)
{
    low[node] = level[node];
    for (auto &it : g[node])
    {
        if (level[it])
        {
            low[node] = min(low[node] , level[it]);
            continue;
        }
        stackk.push({node , it});
        level[it] = level[node] + 1;
        dfs(it);

        if (low[it] >= level[node])
            add_graph({node , it});
        low[node] = min(low[node] , low[it]);

    }
    return ;
}
int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);

    scanf("%d %d", &n, &m);
    for (int i = 1; i<=m; ++i)
    {
        int x , y;
        scanf("%d %d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    level[1] = 1;
    dfs(1);
    printf("%d\n", graphs.size());
    for (auto &vect : graphs)
    {
        for (auto &it : vect)
            printf("%d ", it.second);
        printf("\n");
    }
    return 0;
}