Cod sursa(job #2665006)

Utilizator lauratenderLaura Tender lauratender Data 29 octombrie 2020 21:12:23
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>

using namespace std;
ifstream in ("biconex.in");
ofstream out("biconex.out");

const int MAXN = 100000, MAXM = 200000;
int N, M;
stack <pair <int, int>>  st;
int vis[MAXN + 1], low[MAXN + 1];
vector <int> adj[MAXN + 1];
vector <set <int> > C;

void dfs(int curr, int fd, int cnt)
{
    low[curr] = cnt;
    vis[curr] = cnt;
    for (int nbh: adj[curr])
        if (nbh != fd)
        {
            if (vis[nbh] == 0)
            {
                st.push( make_pair(curr, nbh) );
                dfs(nbh, curr, cnt + 1);
                low[curr] = min(low[curr], low[nbh]);
                if (low[nbh] >= vis[curr])
                    {
                        set <int> con;
                        while (st.top().first != curr || st.top().second != nbh)
                        {
                            con.insert(st.top().first);
                            con.insert(st.top().second);
                            st.pop();
                        }
                        con.insert(curr);
                        con.insert(nbh);
                        st.pop();
                        C.push_back(con);
                    }
            }
            else
                low[curr] = min(low[curr], vis[nbh]);

        }
}

int main()
{
    in >> N >> M;
    int m1, m2;
    for (int i = 0; i < M; ++i)
    {
        in >> m1 >> m2;
        adj[m1].push_back(m2);
        adj[m2].push_back(m1);
    }

    dfs(1, 0, 1);

    out << C.size() << "\n";

    for (int i = 0; i < C.size(); ++i)
    {
         for (auto it = C[i].begin(); it != C[i].end(); it++)
            out << *it << " ";
        out << "\n";
    }
}