Pagini recente » Cod sursa (job #1025407) | Cod sursa (job #1670159) | Cod sursa (job #34747) | Cod sursa (job #2153131) | Cod sursa (job #2842942)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define MAX 100010
using namespace std;
int N,M;
stack<int> Stack;
vector<int>Graf[MAX],Lowlink(MAX,-1),Indx(MAX,-1),ONstack(MAX,0);
vector<vector<int>> ANS;
void Tarjan(int x)
{
static int index = 0;
Indx[x] = Lowlink[x] = index;
index++;
Stack.push(x);
ONstack[x] = 1;
for (int it : Graf[x])
{
if (Indx[it] == -1)
Tarjan(it);
if (ONstack[it])
Lowlink[x] = min(Lowlink[x], Lowlink[it]);
}
if (Indx[x] == Lowlink[x])
{
vector<int> aux;
while (Stack.top() != x)
{
aux.push_back(Stack.top());
ONstack[Stack.top()] = 0;
Stack.pop();
}
aux.push_back(Stack.top());
ONstack[Stack.top()] = 0;
Stack.pop();
ANS.push_back(aux);
}
}
int main()
{
ifstream in ("ctc.in");
ofstream out("ctc.out");
int x,y;
in>>N>>M;
for( int i = 0; i < M; ++i)
{
in>>x>>y;
Graf[x].push_back(y);
}
for(int i = 1; i <=N; ++i)
if (Indx[i] == -1)
Tarjan(i);
out << ANS.size() << "\n";
for (auto it : ANS)
{ for (int x : it)
out<< x << " ";
out << "\n";
}
return 0;
}