Cod sursa(job #2297965)

Utilizator Tataru_AdelinTataru Adelin Tataru_Adelin Data 6 decembrie 2018 21:07:21
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>

using namespace std;

class Node
{
public:
    int index = 0;
    int lowlink = 0;

public:
    void initialize(int x, int y)
    {
        index = x;
        lowlink = y;
    }

    Node()
    {}

    Node(int x, int y)
    {
        initialize(x, y);
    }
};
void dfs(int node, int &nr, vector <vector <int>> &ans, stack <int> &stk, vector <Node> &ind, vector <vector <int>> &path)
{
    ind[node] = Node(nr, nr);
    nr += 1;

    stk.push(node);

    int vec;

    for(unsigned i = 0; i < path[node].size(); i++)
    {
        vec = path[node][i];

        if(ind[vec].index == 0)
            dfs(vec, nr, ans, stk, ind, path);

        ind[node].lowlink = min(ind[node].lowlink, ind[vec].lowlink);
    }


    if(ind[node].index != ind[node].lowlink)
        return;
    vector <int> c;
    int now;

    while(!stk.empty())
    {
        now = stk.top();
        stk.pop();

        c.push_back(now);

        if(ind[now].index == ind[now].lowlink)
            break;
    }

    ans.push_back(c);

}

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int main()
{
    int n, m;
    fin>>n>>m;

    vector <vector <int>> ans;
    stack <int> stk;
    vector <vector <int>> path(n + 1);
    vector <Node> ind(n + 1);


    int x, y;
    for(; m; m--)
    {
        fin>>x>>y;

        path[x].push_back(y);
    }

    int nr = 1;

    for(int i = 1; i <= n; i++)
    {
        if(ind[i].index == 0)
        {
            dfs(i, nr, ans, stk, ind, path);
        }
    }

    fout<<ans.size()<<'\n';

    for(unsigned i = 0; i < ans.size(); i++)
    {
        for(unsigned j = 0; j < ans[i].size(); j++)
            fout<<ans[i][j]<<' ';
        fout<<'\n';
    }


    return 0;
}