Cod sursa(job #2264902)

Utilizator cosceexcosceex cosceex Data 20 octombrie 2018 12:41:46
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
deque < int > m[100005];
stack <pair<int, int> >st;
vector< vector<int> > solutii;
int lvl[100005],low[100005];
bool viz[100005];
int nr;int nr_sol=0;
void comp_bic(int x, int y){
    vector<int>sol;
    int tx; int ty;
    do{
        tx=st.top().first;
        ty=st.top().second;
        st.pop();
        sol.push_back(tx);
        sol.push_back(ty);

    }while(tx!=x or ty!=y);
    sort(sol.begin(),sol.end());
    sol.erase(unique(sol.begin(),sol.end()),sol.end());
    nr_sol++;
    solutii.push_back(sol);
}
void dfs(int node, int t){
    viz[node]=1;
    lvl[node]=lvl[t]+1;
    low[node]=lvl[node];
    for(int i=0;i<m[node].size();i++)
    if(m[node][i]!=t){

        if(viz[m[node][i]]==0){
                if(node==1) nr++;
            st.push(make_pair(node,m[node][i]));
            dfs(m[node][i],node);

            low[node]=min(low[node], low[m[node][i]]);
            if(low[m[node][i]]>=lvl[node]){
                comp_bic(node, m[node][i]);

            }
        }
        else
            low[node]=min(low[node],lvl[m[node][i]]);
    }
}
int main()
{
    int n,mu,i,a,b;
    f>>n>>mu;
    for(i=0;i<=n;i++)
        low[i]=i;
    for(i=1;i<=mu;i++){
        f>>a>>b;
        m[a].push_back(b);
        m[b].push_back(a);
    }
    dfs(1,0);
//    if(nr>1)
//        g<<1<<"\n";
//    for(i=1;i<=n;i++)
//        g<<lvl[i]<<" ";
//    g<<"\n";
//    for(i=1;i<=n;i++)
//        g<<low[i]<<" ";

    g<<nr_sol<<"\n";
    for(i=0;i<nr_sol;i++){
        for(int j=0;j<solutii[i].size();j++)
            g<<solutii[i][j]<<" ";
        g<<"\n";
    }
    return 0;
}