Cod sursa(job #2291960)

Utilizator pistvanPeter Istvan pistvan Data 28 noiembrie 2018 20:25:37
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define MAXN 100001
using namespace std;

vector<int> G[MAXN];
vector<vector<int>> comps;
int N, M, comps_i=-1, dfs_t=1;
int vis[MAXN], lowlink[MAXN];
bool onstack[MAXN];
stack<int> S;

void Read()
{
    ifstream f("ctc.in");
    f>>N>>M;
    for (int i=1;i<=N;i++)
        G[i].push_back(0);
    int a, b;
    for (int i=0;i<M;i++)
    {
        f>>a>>b;
        G[a].push_back(b);
        G[a][0]++;
    }
}

void StrongConnect(int a)
{
    vis[a]=dfs_t;
    lowlink[a]=vis[a];
    S.push(a);
    onstack[a]=1;
    dfs_t++;
    for (int i=1;i<=G[a][0];i++)
    {
        if (vis[G[a][i]]==0) //unvisited
        {
            StrongConnect(G[a][i]);
            lowlink[a]=min(lowlink[a], lowlink[G[a][i]]);
        }
        else if (onstack[G[a][i]]) //visited before, but a precursor
        {
            lowlink[a]=min(lowlink[a], vis[G[a][i]]);
        }
    }
    if (lowlink[a]==vis[a])
    {
        vector<int> tmp;
        comps.push_back(tmp);
        comps_i++;
        while (S.top()!=a)
        {
            comps[comps_i].push_back(S.top());
            onstack[S.top()]=0;
            S.pop();
        }
        comps[comps_i].push_back(a);
        onstack[a]=0;
        S.pop();

    }
}

void Tarjan()
{
    for (int i=1;i<=N;i++)
        if (vis[i]==0)
            StrongConnect(i);
}

void Write()
{
    ofstream g("ctc.out");
    g<<comps.size()<<'\n';
    for (int i=0;i<comps.size();i++)
    {
        for (int j=0;j<comps[i].size();j++)
            g<<comps[i][j]<<' ';
        g<<'\n';
    }
}

int main()
{
    Read();
    Tarjan();
    Write();
}