Pagini recente » Cod sursa (job #2425878) | Cod sursa (job #392695) | Cod sursa (job #2727764) | Cod sursa (job #2082484) | Cod sursa (job #1234775)
#include <cstdio>
#include <vector>
#include <stack>
#include <cstring>
#define FIN "ctc.in"
#define FOUT "ctc.out"
#define MAX 100005
using namespace std;
int num_nodes,
num_arcs;
int num_comp = 0;
vector<int> List1[ MAX ];
vector<int> List2[ MAX ];
vector<int> R[ MAX ];
stack<int> myStack;
bool VIS[MAX];
//function prototypes
void read();
void DFS1(int node);
void DFS2(int node);
void solve();
void displayList();
void write();
int main() {
read();
solve();
write();
return(0);
};
void read() {
int x,y;
freopen(FIN, "r", stdin);
scanf("%d %d", &num_nodes, &num_arcs);
for(; num_arcs;num_arcs--) {
scanf("%d %d", &x, &y);
List1[ x ].push_back( y );
List2[ y ].push_back( x );
}
fclose( stdin );
};
void DFS1(int node) {
VIS[ node ] = true;
for(int i = 0; i < List1[ node ].size(); i++) {
if( !VIS[ List1[ node ][ i ] ]) {
DFS1( List1[ node ][ i ]);
}
}
myStack.push( node );
};
void DFS2(int node) {
VIS[node] = true;
R[ num_comp ].push_back( node );
for(int j = 0; j < List2[ node ].size(); j++) {
if( !VIS[ List2[ node ][ j ] ]) {
DFS2( List2[ node ][ j ] );
}
}
};
void write() {
freopen(FOUT, "w", stdout);
printf("%d\n", num_comp);
for(int num=1; num<=num_comp; num++) {
for(vector<int>::iterator it = R[num].begin(); it != R[num].end(); ++it) {
printf("%d ", *it);
}
printf("\n");
}
fclose( stdin );
};
void solve() {
for(int i = 1; i <= num_nodes; i++)
if( !VIS[ i ] )
DFS1( i );
memset(VIS, false, sizeof(VIS));
while( !myStack.empty() ) {
int node = myStack.top();
myStack.pop();
if( !VIS[ node ] ) {
++num_comp;
DFS2( node );
}
}
}
void displayList() {
for(int i = 1; i<=num_nodes; i++) {
printf("%d -> ", i);
for(int j = 0; j < List2[i].size(); j++) {
printf("%d ", List2[i][j]);
}
printf("\n");
}
}