Pagini recente » Monitorul de evaluare | Cod sursa (job #1511745) | Cod sursa (job #2207508) | Cod sursa (job #1589279) | Cod sursa (job #2617091)
#include <fstream>
#include <vector>
#include <list>
#define NMAX 100100
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int N,M, vis1[NMAX], vis2[NMAX], mark;
vector <int> Ginit[NMAX], G_inv[NMAX];
inline void scan() {
int x,y;
cin>>N>>M;
for(int i=1; i<=M; ++i) {
cin>>x>>y;
Ginit[x].push_back(y);
G_inv[y].push_back(x);
}
}
list <int> List;
inline void dfsmth(int x) {
vis1[x]=1;
for(auto it:Ginit[x])
if(!vis1[it])
dfsmth(it);
List.push_back(x);
}
void dfmark(int x, int smth) {
vis2[x]=smth;
for(auto it: G_inv[x])
if(!vis2[it])
dfmark(it, smth);
}
vector <int> compcon[NMAX];
inline void print() {
cout<<mark<<'\n';
for(int i=1; i<=mark; ++i, cout<<'\n')
for(int j=0; j<compcon[i].size(); ++j)
cout<<compcon[i][j]<<' ';
}
int main()
{
scan();
for(int i=1; i<=N; ++i)
if(!vis1[i])
dfsmth(i);
while(!List.empty()) {
int el=List.back();
if(!vis2[el])
dfmark(el,++mark);
List.pop_back();
}
for(int i=1; i<=N; ++i)
compcon[vis2[i]].push_back(i);
print();
return 0;
}