Cod sursa(job #2534946)

Utilizator stetcoclaudiuStetco Claudiu stetcoclaudiu Data 31 ianuarie 2020 10:33:46
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <fstream>
#include<vector>
#include<algorithm>
#include <iostream>
using namespace std;
ofstream fout("biconex.out");
ifstream fin("biconex.in");
struct muchie
{
    int fiu, tata;
};
muchie S[200005];
vector<int>a[200005];
vector<vector <int> >bi;
int ord[200005],lowLink[200005],cate,nrOrd,varf;
int n,m;
void citire()
{
    int k,x,y;
    fin>>n>>m;
    for(k=1;k<=m;k++)
    {
        fin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
}
void dfs(int nodCurr, int nodTata)
{
    int i,nod,x,y;
    muchie h;
    nrOrd++;
    ord[nodCurr]=lowLink[nodCurr]=nrOrd;
    for(i=0;i<a[nodCurr].size();i++)
    {
        nod=a[nodCurr][i];
        if(ord[nod]==-1)
        {
            varf++;
            S[varf].tata=nodCurr;
            S[varf].fiu=nod;
            dfs(nod,nodCurr);
            lowLink[nodCurr]=min(lowLink[nodCurr],lowLink[nod]);
            if(lowLink[nod]==ord[nodCurr])
            {
                cate++;
                vector<int>aux;
                while(y!=nodCurr || x!=nod)
                {

                   x=S[varf].fiu;
                   y=S[varf].tata;
                   varf--;
                   aux.push_back(x);
                   aux.push_back(y);
                }
                bi.push_back(aux);
            }
        }
        else
            lowLink[nodCurr]=min(lowLink[nodCurr],ord[nod]);
    }
}
int main()
{
    citire();
    int i,j;
    for(i=1;i<=n;i++)
        ord[i]=lowLink[i]=-1;
    S[0].fiu=1;
    S[0].tata=-1;
    dfs(1,0);
    fout<<cate<<"\n";
    for(i=0;i<bi.size();i++)
    {
        sort(bi[i].begin(), bi[i].end());
        bi[i].erase(unique(bi[i].begin(), bi[i].end()), bi[i].end());
        for(j=0;j<bi[i].size();j++)
            fout<<bi[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}