Cod sursa(job #2112065)

Utilizator patcasrarespatcas rares danut patcasrares Data 22 ianuarie 2018 22:29:11
Problema Matrice 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include<fstream>
#include<iostream>
#include<vector>
#include<stack>
#define DN 1005
#define pb push_back
using namespace std;
ifstream fin("traseu.in");
ofstream fout("traseu.out");
int niv[DN],pr[DN],n,m,nr,a,b,f,low[DN],g;
vector<int>v[DN];
vector<int>r[DN];
stack<int>s;
void dfs(int nod)
{
    low[nod]=niv[nod];
    for(auto i:v[nod])
    {
        if(niv[i]==0)
        {
            niv[i]=niv[nod]+1;
            pr[i]=nod;
            dfs(i);
        }
        else
            if(niv[i]<=niv[nod])
            {
                f=nod;
                g=i;
                nr++;
                while(f!=g)
                {
                    if(niv[nod]>niv[i])
                    {
                        r[nr].pb(f);
                        f=pr[f];
                    }
                    else
                    {
                        s.push(g);
                        g=pr[g];
                    }
                }
                r[nr].pb(f);
                while(!s.empty())
                {
                    r[nr].pb(s.top());
                    s.pop();
                }
                if(r[nr].size()<3)
                {
                    r[nr].clear();
                    nr--;
                }
            }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
    }
    for(int i=1;i<=n;i++)
        if(niv[i]==0)
        {

            niv[i]=1;
            dfs(i);
        }
    fout<<nr<<'\n';
    for(int i=1;i<=nr;i++)
    {
        for(auto j:r[i])
            fout<<j<<' ';
        fout<<'\n';
    }
}