Pagini recente » Diferente pentru home intre reviziile 348 si 347 | Monitorul de evaluare | Cod sursa (job #333764) | Cod sursa (job #2201879) | Cod sursa (job #2187714)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int NMAX = 1e5;
int n, m, no;
vector < int > g[1 + NMAX];
vector < int > gi[1 + NMAX];
vector < int > ctc[1 + NMAX];
bitset < 1 + NMAX > vis;
stack < int > st;
bool cmp(vector < int > &a, vector < int > &b) {
return a[0] < b[0];
}
void dfs1(int node) {
vis[node] = 1;
for(int i = 0; i < g[node].size(); i++) {
int to = g[node][i];
if(vis[to] == 0)
dfs1(to);
}
st.push(node);
}
void dfs2(int node) {
vis[node] = 1;
for(int i = 0; i < gi[node].size(); i++) {
int to = gi[node][i];
if(vis[to] == 0)
dfs2(to);
}
ctc[no].push_back(node);
}
int main()
{
in >> n >> m;
for(int i = 1; i <= m; i++) {
int x, y;
in >> x >> y;
g[x].push_back(y);
gi[y].push_back(x);
}
for(int i = 1; i <= n; i++)
if(vis[i] == 0)
dfs1(i);
vis = 0;
while(!st.empty()) {
int node = st.top();
st.pop();
if(vis[node] == 0) {
no++;
dfs2(node);
}
}
for(int i = 1; i <= no; i++)
sort(ctc[i].begin(), ctc[i].end());
sort(ctc + 1, ctc + no + 1, cmp);
out << no << '\n';
for(int i = 1; i <= no; i++) {
for(int j = 0; j < ctc[i].size(); j++)
out << ctc[i][j] << ' ';
out << '\n';
}
in.close();
out.close();
return 0;
}