Pagini recente » Rating bongatonga (opac) | Cod sursa (job #3314552) | Cod sursa (job #3350355) | Cod sursa (job #3310310) | Cod sursa (job #3348418)
#pragma GCC optimize("Ofast")
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
const int NMAX = 100000;
const int MMAX = 200000;
class Graph
{
private:
bool visited[NMAX + 1];
vector<int> adj[NMAX + 1];
vector<int> adj_rev[NMAX + 1];
int n, m;
public:
vector<vector<int>> scc;
vector<vector<int>> adj_compact;
int roots[NMAX + 1];
void init(int n, int m)
{
this->n = n;
this->m = m;
}
void add_dir_edge(int src, int dest)
{
adj[src].push_back(dest);
}
void reverse_edges()
{
for (int i = 1; i <= n; i ++)
{
for (int u : adj[i])
{
adj_rev[u].push_back(i);
}
}
}
void dfs(int nod, vector<int> adja[], vector<int> &output)
{
visited[nod] = 1;
for (auto u : adja[nod])
{
if (!visited[u])
{
dfs(u, adja, output);
}
}
output.push_back(nod);
}
void reset_visited()
{
memset(visited, 0, sizeof(visited));
}
void get_scc_kosaraju()
{
vector<int> order;
reset_visited();
for (int i = 1; i <= n; i ++)
{
if (!visited[i])
{
dfs(i, adj, order);
}
}
reverse_edges();
reset_visited();
for (int i = n - 1; i >= 0; i --)
{
int ind = order[i];
vector<int> component;
if (!visited[ind])
{
dfs(ind, adj_rev, component);
}
if (!component.empty())
{
scc.push_back(component);
int root = *component.begin();
for (auto u : component)
{
roots[u] = root;
}
}
}
adj_compact.assign(n, {});
for (int nod = 1; nod <= n; nod ++)
{
for (auto u : adj[nod])
{
if (roots[nod] != roots[u])
{
adj_compact[roots[nod]].push_back(roots[u]);
}
}
}
}
};
int n, m;
Graph g;
void read()
{
cin >> n >> m;
for (int i = 1; i <= m; i ++)
{
int a, b;
cin >> a >> b;
g.add_dir_edge(a, b);
}
}
void process()
{
g.init(n, m);
g.get_scc_kosaraju();
}
void print_result()
{
cout << g.scc.size() << "\n";
for (auto nodes : g.scc)
{
for (auto nod : nodes)
{
cout << nod << " ";
}
cout << "\n";
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
read();
process();
print_result();
return 0;
}