Pagini recente » Cod sursa (job #3343345) | Cod sursa (job #3346986) | Cod sursa (job #3313845) | Diferente pentru problema/ecexp intre reviziile 11 si 6 | Cod sursa (job #3348417)
#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> rev_adj[NMAX + 1];
int n, m;
public:
vector<vector<int>> scc;
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])
{
rev_adj[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, rev_adj, component);
}
if (!component.empty())
{
scc.push_back(component);
}
}
}
};
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()
{
read();
process();
print_result();
return 0;
}