Pagini recente » Cod sursa (job #2177947) | Cod sursa (job #1230639) | Cod sursa (job #784330) | Cod sursa (job #647955) | Cod sursa (job #2877829)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, m, sol;
vector<vector<int>> G, GT, A;
vector<bool> VC;
stack<int> S;
void dfs_G(int k) {
VC[k] = 1;
for (auto x : G[k])
if (VC[x] == 0)
dfs_G(x);
S.push(k);
}
void dfs_GT(int k) {
VC[k] = 1;
A[sol].push_back(k);
for (auto x : GT[k])
if (VC[x] == 0)
dfs_GT(x);
}
int main() {
cin >> n >> m;
G = GT = A = vector<vector<int>> (n + 1);
for (int i = 1, a, b; i <= m; ++i) {
cin >> a >> b;
G[a].push_back(b);
GT[b].push_back(a);
}
VC = vector<bool> (n + 1, 0);
for (int i = 1; i <= n; ++i)
if (VC[i] == 0)
dfs_G(i);
VC = vector<bool> (n + 1, 0);
while (!S.empty()) {
int k = S.top();
S.pop();
if (VC[k] == 0)
++sol, dfs_GT(k);
}
cout << sol << "\n";
for (int i = 1; i <= sol; ++i, cout << "\n")
for (auto x : A[i])
cout << x << " ";
cin.close();
cout.close();
return 0;
}