Pagini recente » Cod sursa (job #2760262) | Cod sursa (job #523414) | Cod sursa (job #2157006) | Cod sursa (job #2531879) | Cod sursa (job #2487652)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define NMAX 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> G[NMAX], GT[NMAX], rez[NMAX];
stack<int> st;
int viz[NMAX], viz2[NMAX], cnt;
void DFS(int nod)
{
for(int i = 0; i < G[nod].size(); ++i)
if(!viz[G[nod][i]])
{
viz[G[nod][i]] = 1;
DFS(G[nod][i]);
}
st.push(nod);
}
void DFST(int nod)
{
rez[cnt].push_back(nod);
for(int i = 0; i < GT[nod].size(); ++i)
if(!viz2[GT[nod][i]])
{
viz2[GT[nod][i]] = 1;
DFST(GT[nod][i]);
}
}
int main()
{
int n, m;
fin >> n >> m;
for(int i = 1; i <= m; ++i)
{
int x, y;
fin >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
for(int i = 1; i <= n; ++i)
if(!viz[i]){
viz[i] = 1;
DFS(i);
}
while(!st.empty())
{
if(!viz2[st.top()])
{
++cnt;
viz2[st.top()] = 1;
DFST(st.top());
}
st.pop();
}
fout << cnt << '\n';
for(int i = 1; i <= cnt; ++i){
sort(rez[i].begin(), rez[i].end());
for(int j = 0; j < rez[i].size(); ++j)
fout << rez[i][j] << ' ';
fout << '\n';
}
return 0;
}