Pagini recente » Cod sursa (job #2554596) | Cod sursa (job #2548471) | Cod sursa (job #2710305) | Cod sursa (job #57850) | Cod sursa (job #2928479)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int MAXN = 100000;
const int MAXM = 100000;
vector<int> graph[MAXN];
vector<int> reverseGraph[MAXN];
vector<int> nodesOrder;
vector<int> component[MAXN];
int componentSize;
bool marked[MAXN];
void addEdge( int x, int y ){
graph[x].push_back(y);
reverseGraph[y].push_back(x);
}
void dfs( int root, vector<int>& path, vector<int> myGraph[MAXN]){
marked[root] = 1;
int i;
//cout<<root<<'\n';
for( i = 0; i < myGraph[root].size(); i++ ){
if( marked[myGraph[root][i]] == 0 )
dfs( myGraph[root][i], path, myGraph);
}
path.push_back(root);
}
void resetMarked( int n ){
int i;
for( i = 0; i < n; i++ )
marked[i] = 0;
}
int main(){
int n, m, i, j, x, y, root;
in>>n>>m;
for( i = 0; i < m; i++ ){
in>>x>>y;
addEdge( x - 1, y - 1 );
}
// for( i = 0; i < n; i++ ){
// out<<i + 1<<'\n';
// for( j = 0; j < graph[i].size(); j++ ){
// out<<graph[i][j] + 1<<" ";
// }
// out<<'\n';
// }
for( i = 0; i < n; i++ ){
if( marked[i] == 0 )
dfs(i, nodesOrder, graph);
}
resetMarked(n);
// for( i = 0; i < nodesOrder.size(); i++ ){
// out<<nodesOrder[i]<<" ";
// }
// out<<'\n';
while( nodesOrder.size() ){
root = nodesOrder[nodesOrder.size() - 1];
nodesOrder.pop_back();
if( marked[root] == 0 ){
dfs(root, component[componentSize], reverseGraph);
componentSize++;
}
}
out<<componentSize<<'\n';
for( i = 0; i < componentSize; i++ ){
for( j = 0; j < component[i].size(); j++ ){
out<<component[i][j] + 1<<" ";
}
out<<'\n';
}
return 0;
}