Pagini recente » Cod sursa (job #2495026) | Cod sursa (job #335427) | Cod sursa (job #1929443) | Cod sursa (job #968315) | Cod sursa (job #1458516)
#include <stdio.h>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define UNDEF -1
using namespace std;
int N, M, nr = 0, index = 0;
vector< vector<int> > neigh;
vector< vector<int> > components;
vector<int> indx, lowlink;
vector<bool> in_stack;
stack<int> st;
ifstream in("ctc.in");
ofstream out("ctc.out");
void read(){
in >> N >> M;
in_stack.resize(N+1);
indx.resize(N+1);
indx.assign(N+1, UNDEF);
lowlink.resize(N+1);
for(int i = 0; i <= N; ++i){
vector<int> v;
neigh.push_back(v);
components.push_back(v);
}
int x, y;
for(int i = 0; i < M; ++i){
in >> x >> y;
neigh[x].push_back(y);
}
}
void Tarjan(int u){
indx[u] = index;
lowlink[u] = index;
index = index + 1;
st.push(u);
in_stack[u] = true;
int v;
for(unsigned int i = 0; i < neigh[u].size(); ++i){
v = neigh[u][i];
if(indx[v] == UNDEF){
Tarjan(v);
lowlink[u] = min(lowlink[u], lowlink[v]);
}
else if(in_stack[v] == true)
lowlink[u] = min(lowlink[u], indx[v]);
}
if(lowlink[u] == indx[u]){
do{
v = st.top();
st.pop();
in_stack[v] = false;
components[nr].push_back(v);
} while(v != u);
nr++;
}
}
void write(){
out << nr << "\n";
for(int i = 0; i < nr; ++i){
for(unsigned int j = 0; j < components[i].size(); ++j){
out << components[i][j] << " ";
}
out << "\n";
}
}
int main(){
read();
for(int i = 1; i <= N; ++i){
if(indx[i] == UNDEF)
Tarjan(i);
}
write();
}