Pagini recente » Cod sursa (job #1096587) | Cod sursa (job #2313425) | Cod sursa (job #639006) | Cod sursa (job #982218) | Cod sursa (job #1458398)
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
int N, M, count = 0;
stack<int> st;
vector< vector<int> > neigh;
vector< vector<int> > neighT;
vector< vector<int> > components;
vector<bool> visited;
ifstream in("ctc.in");
ofstream out("ctc.out");
void read(){
in >> N >> M;
visited.resize(N+1);
for(int i = 0; i <= N; ++i){
vector<int> v;
vector<int> vT;
vector<int> c;
neigh.push_back(v);
neighT.push_back(vT);
components.push_back(c);
}
int x, y;
for(int i = 0; i < M; ++i){
in >> x >> y;
neigh[x].push_back(y);
neighT[y].push_back(x);
}
}
void DFS(int u){
visited[u] = true;
for(unsigned int i = 0; i < neigh[u].size(); ++i){
int v = neigh[u][i];
if(visited[v] == false)
DFS(v);
}
st.push(u);
}
void DFST(int u){
visited[u] = true;
components[count].push_back(u);
for(unsigned int i = 0; i < neighT[u].size(); ++i){
int v = neighT[u][i];
if(visited[v] == false)
DFST(v);
}
}
void Kosaraju(){
for(int i = 1; i <= N; ++i){
if(visited[i] == false){
DFS(i);
}
}
visited.assign(N+1, false);
while(!st.empty()){
int u = st.top();
st.pop();
if(visited[u] == false){
DFST(u);
count++;
}
}
}
void write(){
out << count << "\n";
for(int i = 0; i < count; ++i){
for(int j = 0; j < components[i].size(); ++j){
out << components[i][j] << " ";
}
out << "\n";
}
}
int main(){
read();
Kosaraju();
write();
}