Pagini recente » Cod sursa (job #2863311) | Cod sursa (job #208795) | Cod sursa (job #2349054) | Cod sursa (job #2572256) | Cod sursa (job #3121975)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, vis[100005];
vector<int>g[100005];
vector<int>rev[100005];
vector<int>components[100005];
int stack_finish_time[100005];
int nr_elem;
int nr_strongly_components;
void dfs(int node)
{
vis[node] = 1;
for (int i = 0; i < g[node].size(); i++)
if (vis[g[node][i]] == 0)
dfs(g[node][i]);
stack_finish_time[++nr_elem] = node;
}
void dfs_inv(int node)
{
vis[node] = 1;
for (int i = 0; i < rev[node].size(); i++)
if (vis[rev[node][i]] == 0)
dfs_inv(rev[node][i]);
components[nr_strongly_components].push_back(node);
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
g[x].push_back(y);
}
for (int i = 1; i <= n; i++) {
if (vis[i] == 0)
dfs(i);
}
for (int i = 1; i <= n; i++)
vis[i] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < g[i].size(); j++)
rev[g[i][j]].push_back(i);
}
for (int i = nr_elem; i >= 1; i--) {
if (vis[stack_finish_time[i]] == 0) {
nr_strongly_components++;
dfs_inv(stack_finish_time[i]);
}
}
fout << nr_strongly_components << '\n';
for (int i = 1; i <= nr_strongly_components; i++) {
for (int j = 0; j < components[i].size(); j++)
fout << components[i][j] << " ";
fout << '\n';
}
return 0;
}