Pagini recente » Cod sursa (job #582113) | Cod sursa (job #2286004) | Cod sursa (job #849138) | Cod sursa (job #863430) | Cod sursa (job #2927703)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <vector>
#define MAXN 100005
using namespace std;
struct XY{
int x,y;
};
vector <int> g[MAXN];
vector <int> revg[MAXN];
vector <int> comp[MAXN];
vector <int> ord;
bool mark[MAXN];
void AddMuchie(XY a){
g[a.x].push_back(a.y);
revg[a.y].push_back(a.x);
}
void SetMark(){
int i;
for(i=0;i<MAXN;i++){
mark[i]=false;
}
}
void dfs(vector <int>* graph,vector<int>& visited,int node){
mark[node]=true;
for(int neigh : graph[node]){
if(mark[neigh]==false){
dfs(graph,visited,neigh);
}
}
visited.push_back(node);
}
int main(){
int n,m,i,noComp,x;
XY a;
FILE *fin,*fout;
fin=fopen("ctc.in","r");
fout=fopen("ctc.out","w");
fscanf(fin,"%d%d",&n,&m);
for(i=0;i<m;i++){
fscanf(fin,"%d%d",&a.x,&a.y);
AddMuchie(a);
}
for(i=1;i<=n;i++){
if(mark[i]==false){
dfs(g,ord,i);
}
}
SetMark();
noComp=0;
while(ord.size()){
x=ord.back();
ord.pop_back();
if(mark[x]==false){
dfs(revg,comp[noComp],x);
noComp++;
}
}
fprintf(fout,"%d\n",noComp);
for(x=0;x<noComp;x++){
while(comp[x].size()>0){
fprintf(fout,"%d ",comp[x].back());
comp[x].pop_back();
}
fprintf(fout,"\n");
}
fclose(fin);
fclose(fout);
return 0;
}