Cod sursa(job #2044828)

Utilizator ioanailincaMoldovan Ioana Ilinca ioanailinca Data 21 octombrie 2017 14:48:58
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 100001;

int n, m;
vector <vector <int> > v;
int index[NMAX], linkerIndex[NMAX];
bool isInStack[NMAX];
int currentIdx, numberOfComponents;
stack <int> stk;
vector <vector <int> > ans;

inline void readData() {
    fin >> n >> m;

    v = vector <vector <int> > (n + 1);

    int x, y;
    while (m--) {
        fin >> x >> y;
        v[x].push_back(y);
    }
}

inline void getNewComponent(int node) {
    int x;
    ++numberOfComponents;
    ans.push_back(vector <int>());
    do {
        x = stk.top();
        stk.pop();
        ans[numberOfComponents - 1].push_back(x);
        isInStack[x] = 0;
    } while (x != node);
    sort(ans[numberOfComponents - 1].begin(), ans[numberOfComponents - 1].end());
}

inline void Tarjan(int node) {
    ++currentIdx;
    index[node] = linkerIndex[node] = currentIdx;
    stk.push(node);
    isInStack[node] = 1;

    for (const int& otherNode: v[node]) {
        if (!index[otherNode]) {
            Tarjan(otherNode);
            linkerIndex[node] = min(linkerIndex[node], linkerIndex[otherNode]);
        }
        else if (isInStack[otherNode]) {
            linkerIndex[node] = min(linkerIndex[node], linkerIndex[otherNode]);
        }
    }

    if (index[node] == linkerIndex[node]) {
        getNewComponent(node);
    }
}

inline void getStronglyConnectedComponents() {
    for (int i = 1; i <= n; ++i)
        if (!index[i]) {
            Tarjan(i);
        }

    fout << numberOfComponents << '\n';
    for (int i = 1; i <= numberOfComponents; ++i) {
        for (const int& t: ans[i - 1])
            fout << t << ' ';
        fout << '\n';
    }
}

int main()
{
    readData();
    getStronglyConnectedComponents();

    fin.close();
    fout.close();
    return 0;
}