Cod sursa(job #2290896)

Utilizator pistvanPeter Istvan pistvan Data 27 noiembrie 2018 10:13:09
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define MAXN 100001
using namespace std;

int N, M;
vector<int> G[MAXN];
vector<int> GT[MAXN];
vector<vector<int>> comps;
int comp_i=0;
int vis[MAXN];
stack<int> L;

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

void Visit(int a)
{
    if (vis[a])
        return;
    vis[a]=-1;
    for (int i=1;i<=G[a][0];i++)
        if (!vis[G[a][i]])
            Visit(G[a][i]);
    L.push(a);
}

void Assign(int a, int root)
{
    if (vis[a]!=-1)
        return;
    vis[a]=root;
    comps[comp_i].push_back(a);
    for (int i=1;i<=GT[a][0];i++)
        Assign(GT[a][i], root);
}

void Kosaraju()
{
    for (int i=1;i<=N;i++)
        if (!vis[i])
            Visit(i);
    int b;
    while(!L.empty())
    {
        b=L.top();
        if (vis[b]==-1)
        {
            vector<int> tmp;
            comps.push_back(tmp);
            Assign(b, b);
            comp_i++;
        }

        L.pop();
    }
    //for (int i=1;i<=N;i++)
    //    cout<<vis[i]<<' ';
}

void Write()
{
    ofstream g("ki.txt");
    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();
    Kosaraju();
    Write();
}