Cod sursa(job #1980628)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 13 mai 2017 17:00:31
Problema Componente biconexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 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;
bool viz[Nmax];
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();
                    fill(viz+1,viz+n+1,false);
                    int tx,ty;
                    do
                    {
                        tx=st.top().first;
                        ty=st.top().second;
                        st.pop();
                        if(!viz[tx]) {v.push_back(tx); viz[tx]=true;}
                        if(!viz[ty]) {v.push_back(ty); viz[ty]=true;}
                    }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++)
    {
        m=ans[i].size();
        for(j=0;j<m;j++)
        g<<ans[i][j]<<' ';
        g<<'\n';
    }

    return 0;
}