Pagini recente » Cod sursa (job #2443950) | Cod sursa (job #1076857) | Cod sursa (job #2946066) | Cod sursa (job #488595) | Cod sursa (job #2928872)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
ifstream in("ctc.in"); //f
ofstream out("ctc.out"); //g
vector <int> graf[100000], con, idx, lowlink, in_stack;
vector < vector <int> > componente;
stack <int> S;
int index;
void print_out(const vector < vector <int> >& G)
{
}
void tarjan(int nod)
{
idx[nod] = index;
lowlink[nod] = index;
index ++;
S.push(nod), in_stack[nod] = 1;
for (auto& vecin : graf[nod]) {
if (idx[vecin] == -1){
tarjan(vecin);
lowlink[nod] = min(lowlink[nod], lowlink[vecin]);
}
else if (in_stack[vecin])
lowlink[nod] = min(lowlink[nod], lowlink[vecin]);
}
if (idx[nod] == lowlink[nod]) {
con.clear();
int node;
do {
con.push_back(node = S.top());
S.pop(), in_stack[node] = 0;
}
while (node != nod);
componente.push_back(con);
}
}
int main()
{
int n, m, x, y;
in >> n >> m;
for (int i = 1; i <= m; i++){
in >> x >> y,
graf[x].push_back(y);
}
idx.resize(n + 1), lowlink.resize(n + 1), in_stack.resize(n + 1);
idx.assign(n + 1, -1), in_stack.assign(n + 1, 0);
for (int i = 1; i <= n; ++ i)
if (idx[i] == -1)
tarjan(i);
out << componente.size() << "\n";
for (int i = 0; i < componente.size(); ++ i) {
for (int j = 0; j < componente[i].size(); ++ j)
out << componente[i][j] << " ";
out << "\n";
}
return 0;
}