Cod sursa(job #3192707)

Utilizator Emmy432622Rotariu Emanuel Emmy432622 Data 13 ianuarie 2024 10:37:16
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5+5;
int n,m;
vector<int>mch[nmax];
int low[nmax],tin[nmax];
bool vis[nmax];
int t;
map<int,bool>ans;
bool v2[nmax];
vector<vector<int>>comps;
vector<int>stiva;

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

void dfs(int i, int p=0)
{
    stiva.push_back(i);
    low[i] = tin[i] = tin[p]+1;
    vis[i] = true;
    for(auto it:mch[i])
    {
        if(it==p)continue;
        if(vis[it])
        {
            low[i] = min(low[i],tin[it]);
        }
        else
        {
            dfs(it,i);
            low[i] = min(low[i],low[it]);
            if(tin[i]<=low[it])
            {
                ans[i]=true;
                comps.push_back(vector<int>());
                while(stiva[stiva.size()-1]!=it)
                {
                    comps[comps.size()-1].push_back(stiva[stiva.size()-1]);
                    stiva.pop_back();
                }
                comps[comps.size()-1].push_back(it);
                stiva.pop_back();
                comps[comps.size()-1].push_back(i);
            }
        }
    }
}

int main()
{
    fin >> n >> m;

    for(int i=1 ; i<=m ; ++i)
    {
        int a,b;
        fin >> a >> b;
        mch[a].push_back(b);
        mch[b].push_back(a);
    }

    for(int i=1 ; i<=n ; ++i)
    {
        if(!vis[i])
        {
            dfs(i);
        }
    }

    /*cout << ans.size() << '\n';
    for(auto it:ans)
    {
        cout << it.first << ' ';
    }*/


    /*for(int i=1 ; i<=n ; ++i)
    {
        cout << low[i] << ' ' ;
    }*/

    fout << comps.size() << '\n';
    for(auto it:comps)
    {
        for(auto it2:it)
            fout << it2 << ' ';
        fout << '\n';
    }


    return 0;
}