Pagini recente » Cod sursa (job #3000536) | Cod sursa (job #737226) | Cod sursa (job #2599496) | Cod sursa (job #629827) | Cod sursa (job #1538382)
#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()
{
ifstream in("ctc.in");
ofstream out("ctc.out");
ios_base::sync_with_stdio(false);
in >> N >> M;
while (M--)
{
int x, y;
in >> x >> y;
G[x].emplace_back(y);
GT[y].emplace_back(x);
}
plus_minus();
out << nrSCC << "\n";
for (int i = 1; i <= nrSCC; ++i)
{
for (int x : SCC[i])
out << x << " ";
out << endl;
}
return 0;
}