Pagini recente » Cod sursa (job #1068334) | Cod sursa (job #1612102) | Cod sursa (job #1472850) | Cod sursa (job #727009) | Cod sursa (job #1919388)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
#define MAX_SIZE 100000
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> G[MAX_SIZE];
stack<int> S;
vector<vector<int>> SOLUTIONS;
int index;
void strongconnect(int v)
{
G[v][0] = index;
G[v][1] = index;
index++;
S.push(v);
G[v][2] = 1;
for(int i = 3; i < G[v].size(); i++)
{
if(G[G[v][i]][0] == -1)
{
strongconnect(G[v][i]);
G[v][1] = min(G[v][1], G[G[v][i]][1]);
}
else if(G[G[v][i]][2] == 1)
{
G[v][1] = min(G[v][1], G[G[v][i]][1]);
}
}
if(G[v][1] == G[v][0])
{
vector<int> sol;
int w;
do
{
w = S.top();
S.pop();
G[w][2] = 0;
sol.push_back(w);
}while(w != v);
SOLUTIONS.push_back(sol);
}
}
int main()
{
int n,m;
fin >> n >> m;
for(int i = 0; i < n; i++)
{
G[i].push_back(-1);
G[i].push_back(-1);
G[i].push_back(0);
}
for(int i = 0; i < m; i++)
{
int x, y;
fin >> x >> y;
G[x- 1].push_back(y - 1);
}
for(int i = 0; i < n; i++)
if(G[i][0] == -1)
strongconnect(i);
fout << SOLUTIONS.size() << '\n';
for(int i = 0; i < SOLUTIONS.size(); i++)
{
for(int j = 0; j < SOLUTIONS[i].size(); j++)
fout << SOLUTIONS[i][j] + 1 << ' ';
fout << '\n';
}
return 0;
}