Pagini recente » Cod sursa (job #1868082) | Cod sursa (job #3151719) | Cod sursa (job #2706775) | Cod sursa (job #1940532) | Cod sursa (job #2928066)
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
using namespace std;
#define MAX_N 100000
vector<int> graph[MAX_N],revGraph[MAX_N],order,comp[MAX_N];
bool viz[MAX_N];
void dfs(vector<int>* graph,vector<int>& vis, int i){
viz[i]=true;
for(int n:graph[i])
if(!viz[n])
dfs(graph,vis,n);
vis.push_back(i);
}
int main(){
FILE *fin,*fout;
int n,m,i,a,b,x,nr;
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,&b);
graph[a-1].push_back(b-1);
revGraph[b-1].push_back(a-1);
}
for(x=0;x<n;x++)
if(!viz[x])
dfs(graph,order,x);
for(i=0;i<n;i++)
viz[i]=false;
nr=0;
while(order.size()){
x=order.back();
order.pop_back();
if(!viz[x]){
dfs(revGraph,comp[nr],x);
nr++;
}
}
fprintf(fout,"%d\n",nr);
for(i=0;i<nr;i++){
for(int j:comp[i]){
fprintf(fout,"%d ",j+1);
}
fprintf(fout,"\n");
}
fclose(fin);
fclose(fout);
return 0;
}