Pagini recente » Cod sursa (job #786333) | Cod sursa (job #526292) | Cod sursa (job #576562) | Cod sursa (job #2792177) | Cod sursa (job #1538383)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000 + 1;
vector<int> G[MAX_N];
vector<int> GT[MAX_N];
vector<int> SCC[MAX_N];
int visited[MAX_N];
int topsort[MAX_N], P;
int N, M;
int nrSCC;
void dfs(int nod)
{
visited[nod] = 1;
for (int v : G[nod])
if (!visited[v])
dfs(v);
topsort[ ++P ] = nod;
}
void dfsT(int nod)
{
SCC[nrSCC].emplace_back(nod);
visited[nod] = 0;
for (int v : GT[nod])
if (visited[v])
dfsT(v);
}
void plus_minus()
{
for (int i = 1; i <= N; ++i)
if (!visited[i])
dfs(i);
for (int i = P; i >= 1; i--)
if (visited[ topsort[i] ])
{
nrSCC++;
dfsT(topsort[i]);
}
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d %d", &N, &M);
while (M--)
{
int x, y;
scanf("%d%d", &x, &y);
G[x].emplace_back(y);
GT[y].emplace_back(x);
}
plus_minus();
printf("%d\n", nrSCC);
for (int i = 1; i <= nrSCC; ++i)
{
for (int x : SCC[i])
printf("%d ", x);
puts("");
}
return 0;
}