Pagini recente » Cod sursa (job #78278) | Cod sursa (job #155309) | Cod sursa (job #2865180) | Cod sursa (job #2446726) | Cod sursa (job #999380)
Cod sursa(job #999380)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <bitset>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define forEACH(G,it) for(vector<int>::iterator it=G.begin();it!=G.end();++it)
using namespace std;
const int Nmax = 100005;
vector <int> G[ Nmax ], Gt[ Nmax ];// graf, graf transpus
vector<int> solution[ Nmax ];
stack <int> answer;
bitset< Nmax > used;
int tare[ Nmax ],N,M,nrt;
void get_graphs(){
scanf("%d%d",&N,&M);
int x,y;
FOR(i,1,M){
scanf("%d%d",&x,&y);
G[ x ].push_back(y);
Gt[ y ].push_back(x);
}
}
void DFS(int nodc){
used[ nodc ] = true;
tare[ nodc ] = 1;
forEACH(G[ nodc ],it)
if(!used[*it])
DFS(*it);
}
void DFS_T(int nodc){
used[ nodc ] = true;
if(tare[ nodc ] == 1)
answer.push(nodc),tare[nodc] = 2;
forEACH(Gt[ nodc ],it)
if(!used[*it])
DFS_T(*it);
}
void baga_sol(){
while(!answer.empty()){
solution[nrt].push_back(answer.top());
answer.pop();
}
++nrt;
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
get_graphs();
FOR(i,1,N)
if(tare[ i ] != 2){
DFS(i);
FOR(j,1,N)
used [ j ] = false;
DFS_T(i);
baga_sol();
}
printf("%d\n",nrt);
FOR(i,0,(nrt-1)){
FOR(j,0,(solution[i].size()-1))
printf("%d ",solution[i][j]);
printf("\n");
}
return 0;
}