Pagini recente » Cod sursa (job #769607) | Cod sursa (job #842585) | Cod sursa (job #2905847) | Cod sursa (job #1405752) | Cod sursa (job #1156148)
#include <fstream>
#include <vector>
#include <iomanip>
#include <stack>
using namespace std;
#define MAX 100001
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<int> normal[MAX], transp[MAX];
stack<int> st;
bool vizN[MAX], vizT[MAX];
vector<int> solutie[MAX];
int solutieN = 0;
void DFS(int x) {
vizN[x] = true;
for (vector<int>::iterator i = normal[x].begin(); i != normal[x].end(); i++) {
if (!vizN[*i]) {
DFS(*i);
}
}
st.push(x);
}
void DFST(int x){
vizT[x] = true;
solutie[solutieN].push_back(x);
for (vector<int>::iterator i = transp[x].begin(); i != transp[x].end(); i++) {
if (!vizT[*i]) {
DFST(*i);
}
}
}
int main() {
int n, k;
in>>n>>k;
for (int i = 1; i <= k; i++) {
int x, y;
in>>x>>y;
normal[x].push_back(y);
transp[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
if (!vizN[i])
DFS(i);
}
while (!st.empty()) {
int x = st.top();
st.pop();
if (!vizT[x]) {
++solutieN;
DFST(x);
}
}
out<<solutieN<<"\n";
for (int i = 1; i <= solutieN; i++){
for (vector<int>::iterator j = solutie[i].begin(); j != solutie[i].end(); j++) {
out<<*j<<" ";
}
out<<"\n";
}
return 0;
}