Cod sursa(job #2371921)

Utilizator BungerNadejde George Bunger Data 6 martie 2019 20:14:59
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>
// Tarjan algorithm
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
const int NMAX=1e5+5;
stack <int> s;
vector<int> G[NMAX];
vector<int> ans[NMAX];
int n,m,x,y,sccCount,id,ids[NMAX],low[NMAX];
bool viz[NMAX],onStack[NMAX];
void read()
{
    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y;
        G[x].push_back(y);
    }
}
void dfs(int nods)
{
    viz[nods]=true;
    s.push(nods);
    onStack[nods]=true;
    ids[nods]=low[nods]=++id;
    for(int i=0;i<G[nods].size();i++)
    {
        int nod=G[nods][i];
        if(!viz[nod]) dfs(nod);
        if(onStack[nod]) low[nods]=min(low[nod],low[nods]);
    }
    if(low[nods]==ids[nods])
        {
            sccCount++;
            while(!s.empty() && s.top()!=nods)
            {
                onStack[s.top()]=false;
                ans[sccCount].push_back(s.top());
                low[s.top()]=ids[nods];
                s.pop();
            }
                onStack[s.top()]=false;
                ans[sccCount].push_back(s.top());
                low[s.top()]=ids[nods];
                s.pop();
        }
}
void out ()
{
    fout<<sccCount<<'\n';
    for(int i=1;i<=sccCount;i++)
    {
        for(int j=0;j<ans[i].size();j++)
            fout<<ans[i][j]<<" ";
        fout<<'\n';
    }
}
int main()
{
    read();
    for(int i=1;i<=n;i++)
        if(!viz[i]) dfs(i);
    out();
    return 0;
}