Pagini recente » Cod sursa (job #1422573) | Cod sursa (job #1409592) | Cod sursa (job #1532073) | Cod sursa (job #1921442) | Cod sursa (job #3124107)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m, x, y, viz[100005], ctc;
vector<int>v1[100005], v2[100005], CT[100005];
stack<int>s;
void read() {
f >> n;
f >> m;
for (int i = 1; i <= m; i++)
f >> x >> y, v1[x].push_back(y), v2[y].push_back(x);
}
void DFS(int nod) {
viz[nod] = 1;
for (int i = 0; i < v1[nod].size(); i++)
{
int vecin = v1[nod][i];
if (viz[vecin] == 0)DFS(vecin);
}
s.push(nod);
}
void DFS_TR(int nod) {
viz[nod] = 2;
CT[ctc].push_back(nod);
for (int i = 0; i < v2[nod].size(); i++)
if (viz[v2[nod][i]] == 1)DFS_TR(v2[nod][i]);
}
void solve() {
for (int i = 1; i <= n; i++)
if (viz[i] == 0)
{
DFS(i);
}
while (s.size()) {
int nod = s.top();
if (viz[nod] == 1) {
ctc++;
DFS_TR(nod);
}
s.pop();
}
}
void print() {
g << ctc << '\n';
for (int i = 1; i <= ctc; i++,g<<"\n")
for (int j = 0; j < CT[i].size(); j++)
g << CT[i][j] << " ";
}
int main() {
read();
solve();
print();
}