Cod sursa(job #2367046)

Utilizator Horea_Mihai_SilaghiHorea Mihai Silaghi Horea_Mihai_Silaghi Data 5 martie 2019 01:20:42
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <fstream>
#include <vector>
#include <stack>
#include <iterator>
#define maxn 100005
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector <int> v[maxn],on_stack, index, low_index,viz,con;

vector < vector<int> > c;
stack <int> s;
int val=0,cnt=0,n;

void citire()
{
    int m,x,y;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
    }
}

void tarjan(int i)
{
    int l,j;
    val++;
    on_stack[i]=1;
    index[i]=val;
    low_index[i]=val;
    viz[i]=1;
    l=v[i].size();
    s.push(i);
    for(j=0;j<l;j++)
    {
        if(viz[v[i][j]]==0)
        {
            tarjan(v[i][j]);
            low_index[i]=min(low_index[i],low_index[v[i][j]]);
        }
        else
        {
            if(on_stack[v[i][j]]==1)
                low_index[i]=min(low_index[i],low_index[v[i][j]]);
        }
    }
    if(index[i]==low_index[i])
    {
        cnt++;
        int node=s.top();
        con.clear();
        do
        {
            node=s.top();
            con.push_back(node);
            s.pop();
            on_stack[node]=0;
        }while(node!=i);
        c.push_back(con);
    }
}
int main()
{
    int i;
    citire();
    viz.resize(n+1);on_stack.resize(n+1);index.resize(n+1);low_index.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);
        }
    cout<<cnt<<'\n';
    for(int i=0;i<cnt;i++)
    {
        for(int j=0;j<c[i].size();j++)
            cout<<c[i][j]<<" ";
        cout<<'\n';
    }
    return 0;
}