Cod sursa(job #2261752)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 16 octombrie 2018 17:12:04
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <bits/stdc++.h>
#define Nmax 100001
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
list <int> G[Nmax];
int dfn[Nmax];
int low[Nmax];
int N,nr,n;
vector < vector<int> > ans;
stack < pair <int,int> > st;
vector <int> v;
void DFS(int x, int t)
{
    list <int> :: iterator it;
    dfn[x]=low[x]=++N;
    for(it=G[x].begin();it!=G[x].end();it++)
    {
        if(*it!=t)
        {
            if(dfn[*it]==-1)
            {
                st.push({*it,x});
                DFS(*it,x);
                low[x]=min(low[x],low[*it]);
                if(low[*it]>=dfn[x])
                {
                    nr++;
                    v.clear();
                    int tx,ty;
                    do
                    {
                        tx=st.top().first;
                        ty=st.top().second;
                        st.pop();
                        v.push_back(tx);
                        v.push_back(ty);
                    }while(tx!=*it or ty!=x);
                    ans.push_back(v);
                }
            }
            else if(*it!=t)
                low[x]=min(low[x],dfn[*it]);
        }
    }
}
int main()
{
    int m,i,j;
    f>>n>>m;
    for(int con=1;con<=m;con++)
    {
        f>>i>>j;
        G[i].push_back(j);
        G[j].push_back(i);
    }
    fill(dfn+1,dfn+n+1,-1);
    fill(low+1,low+n+1,-1);
    DFS(1,-1);
    g<<nr<<'\n';
    for(i=0;i<nr;i++)
    {
        sort(ans[i].begin(),ans[i].end());
        ans[i].erase(unique(ans[i].begin(),ans[i].end()),ans[i].end());
        for(j=0;j<ans[i].size();j++)
            g<<ans[i][j]<<' ';
        g<<'\n';
    }

    return 0;
}