Pagini recente » Cod sursa (job #2207326) | Cod sursa (job #2778443) | Cod sursa (job #383474) | Cod sursa (job #2216932) | Cod sursa (job #3296198)
#include <bits/stdc++.h>
const int MAXN = 100'000;
const int MAXP2 = 65'536;
int n, m;
std::vector<int> adj[MAXN + 1];
bool viz[MAXN + 1];
struct Queue{
int que[MAXN + 1];
int first, last;
void init() {
first = last = 0;
}
void push(int x) {
que[last++] = x;
}
void pop() {
first++;
}
int front() {
return que[first];
}
bool empty() {
return last == first;
}
};
void bfs(int node) {
Queue q;
for( int i = 1; i <= n; i++ )
viz[i] = 0;
q.push(node);
viz[node] = 1;
while(!q.empty()) {
int node = q.front();
q.pop();
for( int nxt : adj[node] ) {
if(!viz[nxt]) {
q.push(nxt);
viz[nxt] = 1;
}
}
}
}
FILE *fin, *fout;
void openFiles() {
fin = fopen("ctc.in", "r");
fout = fopen("ctc.out", "w");
}
void closeFiles() {
fclose(fin);
fclose(fout);
}
struct Kosaraju {
std::vector<int> tadj[MAXN + 1];
bool viz[MAXN + 1];
int postord[MAXN + 1];
int nrp = 0;
void transpose_graph() {
for( int i = 1; i <= n; i++ ) {
for( int node : adj[i] )
tadj[node].push_back(i);
}
}
void dfs1(int node) {
viz[node] = 1;
for(int nxt : adj[node]) {
if(!viz[nxt])
dfs1(nxt);
}
postord[nrp++] = node;
}
void reset_viz() {
for( int i = 1; i <= n; i++ )
viz[i] = 0;
}
void dfs2(int node, std::vector<int> &v) {
viz[node] = 1;
v.push_back(node);
for( int nxt : tadj[node] ) {
if(!viz[nxt])
dfs2(nxt, v);
}
}
void get_scc() {
for( int i = 1; i <= n; i++ ) {
if(!viz[i])
dfs1(i);
}
reset_viz();
std::vector<std::vector<int>> sol;
for( int i = n - 1; i >= 0; i-- ) {
if(!viz[postord[i]]) {
std::vector<int> v;
dfs2(postord[i], v);
sol.push_back(v);
}
}
fprintf(fout, "%d\n", sol.size());
for( std::vector<int> &v : sol ) {
for( int x : v ) {
fprintf(fout, "%d ", x);
}
fprintf(fout, "\n");
}
}
}kosaraju;
int main(){
openFiles();
fscanf(fin, "%d%d", &n, &m);
for( int i = 0; i < m; i++ ) {
int u, v;
fscanf(fin, "%d%d", &u, &v);
adj[u].push_back(v);
}
kosaraju.transpose_graph();
kosaraju.get_scc();
closeFiles();
return 0;
}