Pagini recente » Cod sursa (job #2042480) | Cod sursa (job #1669283)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int N_MAX = 100001;
vector <int> G[N_MAX];
vector <int> sol[N_MAX];
stack <int> S;
int lowlink[N_MAX];
bool in_stiva[N_MAX];
int n, m, index, total;
int idx[N_MAX];
void read()
{
int x, y;
f>>n>>m;
for (int i=1; i<=m; i++)
f>>x>>y,G[x].push_back(y);
}
void dfs(int nod)
{
index++;
idx[nod] = index;
lowlink[nod] = index;
S.push(nod);
in_stiva[nod] = true;
for (int i : G[nod])
if (!lowlink[i])
dfs(i), lowlink[nod] = min(lowlink[nod], lowlink[i]);
else
if (in_stiva[i])
lowlink[nod] = min(lowlink[nod], lowlink[i]);
if (lowlink[nod] == idx[nod])
{
int it;
it = S.top();
total ++;
while (it != nod)
{
sol[total].push_back(it);
in_stiva[it] = false;
S.pop();
it = S.top();
}
sol[total].push_back(it);
S.pop();
in_stiva[it] = false;
}
}
void write()
{
g<<total<<"\n";
for (int i=1; i<=total; i++)
{
for (int j : sol[i])
g<<j<<" ";
g<<"\n";
}
}
int main()
{
read();
for (int i=1; i<=n; i++)
{
if (!lowlink[i])
dfs(i);
}
write();
return 0;
}