Cod sursa(job #1690000)

Utilizator lupvasileLup Vasile lupvasile Data 14 aprilie 2016 18:00:56
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>
using namespace std;
#ifdef INFOARENA
#define cout fout
ifstream fin("biconex.in");
ofstream fout("biconex.out");
#else
ifstream fin("date.in");
#endif // INFOARENA

/// ///////////////////////////////////////////

void read();

#define nmax 100010
#define inf 0x3f3f3f3f

vector<int> G[nmax],G_t[nmax];
vector<vector<int>> ctc;
bool viz[nmax];
int st[nmax],n,low[nmax],lev[nmax];

void dfs(int nod,int fat,int level)
{
    low[nod]=level;
    lev[nod]=level;
    viz[nod]=1;

    st[++st[0]]=nod;

    for(auto vec:G[nod])
    {
        if(vec==fat) continue;

        if(viz[vec]) low[nod]=min(low[nod],lev[vec]);
        else
        {
            dfs(vec,nod,level+1);
            low[nod]=min(low[nod],low[vec]);


            if(low[vec]>=level)
            {
                ctc.push_back(vector<int>());
                for(; st[st[0]]!=vec; --st[0])
                    ctc.back().push_back(st[st[0]]);
                --st[0];
                ctc.back().push_back(vec);
                ctc.back().push_back(nod);
            }
        }
    }
}

int main()
{
    read();

    for(int i=1;i<=n;++i)
        if(!viz[i]) dfs(i,0,1);

    cout<<ctc.size()<<'\n';
    for(auto &comp:ctc)
    {
        for(auto &it:comp) cout<<it<<' ';
        cout<<'\n';
    }

}
void read()
{
    int x,y,c,m;
    fin>>n>>m;
    for(; m; --m)
    {
        fin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}