Pagini recente » Clasamentul arhivei educationale | Clasamentul arhivei educationale | Clasamentul arhivei educationale | Cod sursa (job #2427194) | Cod sursa (job #2474125)
#include <bits/stdc++.h>
#define N_MAX 100000
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
vector<vector<int>> graph(N_MAX, vector<int>());
vector<vector<int>> sol;
vector<bool> onStack(N_MAX, false);
vector<bool> visited(N_MAX, false);
vector<int> id(N_MAX);
vector<int> low(N_MAX);
stack<int> Stack;
int t = 0;
void find_ctc(int node)
{
visited.at(node) = true;
++t;
id.at(node) = t;
low.at(node) = t;
Stack.push(node);
onStack.at(node) = true;
for(auto& next : graph.at(node))
{
if(visited.at(next) == false) find_ctc(next);
if(onStack.at(next) == true) low.at(node) = min(low.at(node), low.at(next));
}
if(low.at(node) == id.at(node))
{
vector<int> ctc;
while(Stack.top() != node)
{
onStack.at(Stack.top()) = false;
ctc.push_back(Stack.top());
Stack.pop();
}
onStack.at(Stack.top()) = false;
ctc.push_back(Stack.top());
Stack.pop();
sol.push_back(ctc);
}
}
int main()
{
fin >> n >> m;
for(int x, y, i = 1; i <= m; ++i)
{
fin >> x >> y;
graph.at(x).push_back(y);
}
for(int i = 1; i <= n; ++i)
{
if(visited.at(i) == false)
{
find_ctc(i);
}
}
fout << sol.size() << '\n';
for(auto& ctc : sol)
{
for(auto& node : ctc) fout << node << ' ';
fout << '\n';
}
}