Cod sursa(job #2579268)

Utilizator T_george_TGeorge Teodorescu T_george_T Data 12 martie 2020 12:16:55
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int NMAX=100004;
vector <int>g[NMAX],ans;
vector <vector<int>>sol;
stack<pair<int,int>>s;
int n,m,low[NMAX],val[NMAX];
bool seen[NMAX];
void DFS(int node){
    seen[node]=1;
    for(auto y:g[node])
        if(!seen[y]) DFS(y);
}
void add_sol(int a,int b){
    vector<int>c;
    int node1,node2;
    do{
         node1=s.top().first,node2=s.top().second;
        s.pop();
        c.push_back(node1),c.push_back(node2);
    }while(node1!=a || node2!=b);
    sol.push_back(c);
}
void dfs(int node,int nb){
    val[node]=low[node]=nb;
    for(auto y:g[node]){
        if(val[y]==-1){
            s.push({node,y});
            dfs(y,nb+1);
            low[node]=min(low[node],low[y]);
            if(low[y]>=val[node]) add_sol(node,y);
        }
        else
            low[node]=min(low[node],val[y]);
    }
}
int main()
{
    in>>n>>m;
    for(int i=1,a,b;i<=m;i++){
        in>>a>>b;
        g[a].push_back(b),g[b].push_back(a);
    }
   /* for(int i=1;i<=n;i++)
        if(!seen[i]){
            ans.push_back(i);
            DFS(i);
        }
    out<<ans.size()<<'\n';
    for(auto y:ans)
        out<<y<<" ";*/

    memset(val,-1,sizeof(val));
    dfs(1,0);
    out<<sol.size()<<'\n';
    for(int i=0;i<sol.size();i++){
        sort(sol[i].begin(),sol[i].end());
        vector<int>::iterator dr=unique(sol[i].begin(),sol[i].end());
        for(vector<int>::iterator k=sol[i].begin();k!=dr;k++)
            out<<*k<<" ";
        out<<'\n';
    }
    return 0;
}