Pagini recente » Cod sursa (job #1525323) | Cod sursa (job #485659) | Cod sursa (job #496393) | Cod sursa (job #586368) | Cod sursa (job #2027572)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#define MAX 100005
using namespace std;
int n, m, x, y;
vector<int> l[MAX], r[MAX];
stack<int> s;
bool viz[MAX], vizr[MAX];
vector<int> c;
vector<vector<int> > ctc;
void dfs(int x) {
viz[x] = 1;
for(int i = 0; i < l[x].size(); ++i)
if(!viz[l[x][i]])
dfs(l[x][i]);
s.push(x);
}
void dfsr(int x) {
c.push_back(x);
vizr[x] = 1;
for(int i = 0; i < r[x].size(); ++i)
if(!vizr[r[x][i]])
dfsr(r[x][i]);
}
int main() {
ifstream f("ctc.in");
ofstream g("ctc.out");
f >> n >> m;
for(int i = 0; i < m; ++i) {
f >> x >> y;
l[x].push_back(y);
r[y].push_back(x);
}
for(int i = 1; i <= n; ++i)
if(!viz[i])
dfs(i);
while(!s.empty()) {
int x = s.top();
s.pop();
if(!vizr[x]) {
dfsr(x);
ctc.push_back(c);
c.clear();
}
}
g << ctc.size() << "\n";
for(int i = 0; i < ctc.size(); ++i) {
for(int j = 0; j < ctc[i].size(); ++j)
g << ctc[i][j] << " ";
g << "\n";
}
return 0;
}