Cod sursa(job #2241519)

Utilizator unknownpersonBidasca Carina Georgiana unknownperson Data 16 septembrie 2018 11:27:31
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int N = 100010;
const int M = 200010;
int n,m,top,x[M],y[M],niv[N],up[N],st[2*M];
vector<int> v[N];
vector<vector<int>> C;
void DF(int,int);
int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        f>>x[i]>>y[i];
        v[x[i]].push_back(i);
        v[y[i]].push_back(i);
    }
    for(int i=1; i<=n; i++)
    {
        if(!v[i].size())
        {
            C.push_back(vector<int>(1,i));
            continue;
        }
        if(!niv[i])
            DF(i,0);
    }
    g<<C.size()<<'\n';
    for(auto comp:C)
    {
        for(auto it:comp)
            g<<it<<' ';
        g<<'\n';
    }
    return 0;
}
void DF(int nod,int tata)
{
    niv[nod]=up[nod]=niv[tata]+1;
    for(auto edge:v[nod])
    {
        int vec=x[edge]+y[edge]-nod;
        if(vec==tata)continue;
        if(!niv[vec])
        {
            st[++top]=x[edge];
            st[++top]=y[edge];
            DF(vec,nod);
            up[nod]=min(up[nod],up[vec]);
            if(niv[nod]<=up[vec])
            {
                vector<int> c;
                c.resize(0);
                int i,j;
                for(i=top,j=top-1;; i-=2,j-=2)
                    if(st[j]==x[edge]&&st[i]==y[edge])
                        break;
                sort(st+j,st+top+1);
                c.push_back(st[top]);
                for(i=top-1; i>=j; i--)
                    if(st[i]!=st[i+1])
                        c.push_back(st[i]);
                top=i;
                C.push_back(c);
            }
        }
        else
            up[nod]=min(up[nod],up[vec]);
    }
}