Pagini recente » Cod sursa (job #1477150) | Cod sursa (job #790879) | Cod sursa (job #1258725) | Cod sursa (job #2842859) | Cod sursa (job #3242684)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define nl '\n'
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 100000;
int n, m, nrc;
vector<int> g[NMAX+1], ctc[NMAX+1];
int d[NMAX+1], dmin[NMAX+1], timp = 0;
stack<int> s;
bool inSt[NMAX+1];
void citire()
{
int x, y;
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
fin >> x >> y;
g[x].push_back(y);
}
return;
}
void dfs(int x)
{
d[x] = ++timp;
dmin[x] = d[x];
s.push(x);
inSt[x] = 1;
for (auto &y : g[x])
{
if (d[y] == 0)
{
dfs(y);
dmin[x] = min(dmin[x], dmin[y]);
}
else
{
if (inSt[y] == 1)
dmin[x] = min(dmin[x], d[y]);
}
}
if (dmin[x] == d[x])
{
int u;
nrc++;
do
{
u = s.top();
ctc[nrc].push_back(u);
s.pop();
inSt[u] = 0;
}
while (x != u);
}
}
void afisare()
{
fout << nrc << nl;
for (int i = 1; i <= nrc; i++)
{
for (auto &x : ctc[i])
fout << x << ' ';
fout << nl;
}
return;
}
int main()
{
citire();
for (int i = 1; i <= n; i++)
{
if (d[i] == 0)
dfs(i);
}
afisare();
return 0;
}