Cod sursa(job #2447354)

Utilizator AndreiStanescuAlloys Nokito AndreiStanescu Data 12 august 2019 23:12:44
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include<vector>
#include<fstream>
#include<iostream>
#include<stack>
#define N 100000
using namespace std;

int n,m,disc[N],low[N],In_stack[N],scc;
vector<int> G[N],sol[N];
stack<int> S;

void read()
{
    int x,y;
    ifstream fin("ctc.in");
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        G[x].push_back(y);
    }
    fin.close();
}


void Tarjan(int u,int &time)
{
    disc[u]=low[u]=++time;
    S.push(u);
    In_stack[u]=1;
    vector<int>::iterator it;
    for(it=G[u].begin();it!=G[u].end();it++)
    {
        int v=*it;
        if(!disc[v])
        {
            Tarjan(v,time);
            low[u]=min(low[u],low[v]);
        }
        else
            if(In_stack[v])
                low[u]=min(low[u],disc[v]);
    }

    if(low[u]==disc[u])
    {
        int w=0;
        ++scc;
        while(S.top()!=u)
        {
            sol[scc].push_back(S.top());
            In_stack[S.top()]=0;
            S.pop();
        }
        sol[scc].push_back(u);
        In_stack[u]=0;
        S.pop();
    }


}


void solve()
{
    int start=0;
    for(int i=1;i<=n;i++)
        if(!disc[i])
        Tarjan(i,start);
    ofstream fout("ctc.out");
    fout<<scc<<'\n';
    for(int i=1;i<=scc;i++)
    {
        vector<int>::iterator it;
        for(it=sol[i].begin();it!=sol[i].end();it++)
        fout<<(*it)<<' ';
        fout<<'\n';
    }
    fout.close();
}



int main()
{
    read();
    solve();
}