Cod sursa(job #2561441)

Utilizator Vladymyr11Pechi Vladimir Stefan Vladymyr11 Data 28 februarie 2020 19:52:13
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <fstream>
#include <vector>
#include <stack>
#include <iterator>

using namespace std;

#define MAXN  100000
#define Min(a, b)  ((a) < (b) ? (a) : (b))

vector <int> adj[MAXN],con,idx,lowlink,in_stack;
vector <vector <int> > G;
stack <int> S;
int n,m,x,y,indecs;
void citire()
    {
    ifstream fin ("ctc.in");
    fin>>n>>m;
    for (int i=1;i<=m;i++)
        {
        fin>>x>>y;
        adj[x-1].push_back(y-1);
        }
    fin.close();
    }
void afisare()
    {
    ofstream fout ("ctc.out");
    int l1=G.size();
    fout<<l1<<"\n";
    for (int i=0;i<l1;i++)
        {
        int l2=G[i].size();
        for (int j=0;j<l2;j++)
            fout<<G[i][j]+1<<" ";
        fout<<"\n";
        }
    fout.close();
    }
void tarjan(int n)
    {
    idx[n]=lowlink[n]=indecs;
    indecs++;
    S.push(n),in_stack[n]=1;
    vector <int>::const_iterator it;
    for (it = adj[n].begin();it!=adj[n].end();it++)
        {
        if (idx[*it]==-1)
            {
            tarjan(*it);
            lowlink[n]=Min(lowlink[n], lowlink[*it]);
            }
        else if (in_stack[*it])
            lowlink[n]=Min(lowlink[n],lowlink[*it]);
        }
    if (idx[n] == lowlink[n])
        {
        con.clear();
        int node;
        do {
            node=S.top();
            con.push_back(node);
            S.pop();
            in_stack[node]=0;
            }
        while (node != n);
        G.push_back(con);
        }
    }
int main ()
    {
    citire();
    idx.resize(n);
    lowlink.resize(n);
    in_stack.resize(n);
    idx.assign(n,-1);
    in_stack.assign(n,0);
    for (int i=0;i<n;i++)
        if (idx[i]==-1)
            tarjan(i);
    afisare();
    return 0;
    }