Pagini recente » Cod sursa (job #1544654) | Cod sursa (job #2191431) | Cod sursa (job #2853985) | Cod sursa (job #1584072) | Cod sursa (job #2214605)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N, M, x, y, k, s, Q[100003], visit[100003];
vector<int> G[100003], GT[100003], sol[100003];
void df(int x) {
visit[x] = true;
for(int i = 0; i < G[x].size(); i++)
if(!visit[G[x][i]]) df(G[x][i]);
Q[++k] = x;
}
void df_transpus(int x) {
visit[x] = true;
for(int i = 0; i < GT[x].size(); i++)
if(!visit[GT[x][i]])
df_transpus(GT[x][i]);
sol[s].push_back(x);
}
int main()
{
f >> N >> M;
for(int i = 1; i <= M; i++) {
f >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
for(int i = 1; i <= N; i++)
if(!visit[i])
df(i);
for(int i = 1; i <= N; i++)
visit[i] = false;
for(int i = N; i >= 1; i--) {
int x = Q[i];
if(!visit[x]) {
s++;
df_transpus(x);
}
}
g << s << "\n";
for(int i = 1; i <= s; i++) {
for(int j = 0; j < sol[i].size(); j++)
g << sol[i][j] << " ";
g << "\n";
}
return 0;
}