Pagini recente » Cod sursa (job #1845512) | Cod sursa (job #812872) | Cod sursa (job #1953421) | Cod sursa (job #1988065) | Cod sursa (job #3296206)
#include <bits/stdc++.h>
const int MAXN = 100'000;
const int MAXP2 = 65'536;
const int BUFSIZE = 131'072;
int n, m;
std::vector<int> adj[MAXN + 1];
FILE *fin, *fout;
void openFiles() {
fin = fopen("ctc.in", "r");
fout = fopen("ctc.out", "w");
}
void closeFiles() {
fclose(fin);
fclose(fout);
}
char rbuf[BUFSIZE];
int rpos = BUFSIZE - 1;
char readChar() {
if(!(rpos = (rpos + 1) & (BUFSIZE - 1)))
fread(rbuf, 1, BUFSIZE, fin);
return rbuf[rpos];
}
int readInt() {
char ch;
while(!isdigit(ch = readChar()));
int nr = 0;
do{
nr = nr * 10 + ch - '0';
}while(isdigit(ch = readChar()));
return nr;
}
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();
n = readInt();
m = readInt();
for( int i = 0; i < m; i++ ) {
int u, v;
u = readInt();
v = readInt();
adj[u].push_back(v);
}
kosaraju.transpose_graph();
kosaraju.get_scc();
closeFiles();
return 0;
}