Pagini recente » Cod sursa (job #421215) | Cod sursa (job #1482531) | Cod sursa (job #1503526) | Cod sursa (job #2589043) | Cod sursa (job #1548022)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
const int NMAX = 100005;
const int BMAX = 500;
char buffer[BMAX + 1];
int poz = BMAX ;
vector < int > G[NMAX],Gi[NMAX],Gf[NMAX],where;
bitset < BMAX > viz;
stack < int > bumt;
void parsare(int &x){
while(!isdigit(buffer[poz])){
poz ++;
if(poz > BMAX){
poz = 0;
fin.read(buffer,BMAX);
}
}
x = 0;
while(isdigit(buffer[poz])){
x = x*10 + (buffer[poz] - '0');
poz++;
if(poz > BMAX){
poz = 0;
fin.read(buffer,BMAX);
}
}
}
void dfs(int nod){
viz[nod] = 1;
for(int i = 0;i < Gi[nod].size(); i++){
if(viz[Gi[nod][i]] == 0)
dfs(Gi[nod][i]);
}
bumt.push(nod);
}
void dms(int nod,int cont){
where[nod] = cont;
for(int i = 0; i < Gf[nod].size();i++){
if(where[Gf[nod][i]] == 0){
dms(Gf[nod][i],cont);
}
}
}
int main()
{
int n,m,x,y,cont;
parsare(n); parsare(m);
for(int i = 1; i <= m; i++){
parsare(x); parsare(y);
Gi[x].push_back(y);
Gf[y].push_back(x);
}
for(int i = 1;i <= n; i++){
if(viz[i] == 0){
dfs(i);
}
}
where.resize( n + 1);
cont = 1;
while(!bumt.empty()){
if(where[bumt.top()] == 0){
dms(bumt.top(),cont);
cont ++;
}
bumt.pop();
}
for(int i = 1; i <= n; i++){
G[where[i]].push_back(i);
}
fout << cont - 1 << "\n";
for(int j = 1; j < cont; j++){
for(int i = 0; i < G[j].size();i++){
fout << G[j][i] << " ";
}
fout << "\n";
}
return 0;
}