Cod sursa(job #2369395)

Utilizator Horea_Mihai_SilaghiHorea Mihai Silaghi Horea_Mihai_Silaghi Data 5 martie 2019 22:56:04
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.19 kb
#include <fstream>
#include <vector>
#include <stack>
#define maxn 100005
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");

vector <int> index,low_index,con,origin;
vector <bool> viz,on_stack;
vector < vector<int> > c,v,a;
stack <int> s;
int val=0,cnt=0,n;
void citire()
{
    int x,y,i,m;
    in>>n>>m;
    v.resize(n+1);
    a.resize(n+1);
    for(i=1;i<=m;i++)
    {
        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
        a[x].push_back(0);
        a[y].push_back(0);
    }
}
void tarjan(int x)
{
    int i,node,l,j;
    val++;
    viz[x]=1;
    s.push(x);
    index[x]=val;
    low_index[x]=val;
    on_stack[x]=1;
    l=v[x].size();
    for(i=0;i<l;i++)
    {
        if(viz[v[x][i]]==0&&a[x][i]==0)
        {
            origin[v[x][i]]=x;
            a[x][i]=1;
            for(j=0;j<v[v[x][i]].size();j++)
                if(x==v[v[x][i]][j])
                    a[v[x][i]][j]=1;
            tarjan(v[x][i]);
            low_index[x]=min(low_index[x],low_index[v[x][i]]);
        }
        else
        {
            if(on_stack[v[x][i]]==1&&a[x][i]==0)
                low_index[x]=min(low_index[x],low_index[v[x][i]]);
        }
    }
    if(index[x]==low_index[x])
    {
        if(origin[x]!=0)
        {
            con.clear();
            cnt++;
            con.push_back(x);
            con.push_back(origin[x]);
            c.push_back(con);
        }
        con.clear();
        cnt++;
        do
        {
            node=s.top();
            s.pop();
            con.push_back(node);
            on_stack[node]=0;
        }while(node!=x);
        if(con.size()>1)
            c.push_back(con);
        else
            cnt--;
    }
}
int main()
{
    int i,j;
    citire();
    on_stack.resize(n+1);index.resize(n+1);low_index.resize(n+1);viz.resize(n+1);origin.resize(n+1);
    viz.assign(n+1,0);on_stack.assign(n+1,0);
    for(i=1;i<=n;i++)
        if(viz[i]==0)
        {
            tarjan(i);
        }
    out<<cnt<<'\n';
    for(i=0;i<cnt;i++)
    {
        for(j=0;j<c[i].size();j++)
            out<<c[i][j]<<" ";
        out<<'\n';
    }
    return 0;
}