Pagini recente » Cod sursa (job #1998573) | Cod sursa (job #1325892) | Cod sursa (job #1557168) | Cod sursa (job #784881) | Cod sursa (job #2681257)
#include <fstream>
#include <vector>
#include <stack>
#define maxSize 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> nodes[maxSize],transpus[maxSize],ctc[maxSize];
int n,m,k,visited[maxSize];
stack<int> s;
void read(){
fin>>n>>m;
int x,y;
for(int i=0; i<m; i++){
fin>>x>>y;
nodes[x].push_back(y);
transpus[y].push_back(x);
}
}
void dfs(int node){
visited[node]=1;
for(auto it: nodes[node])
if(visited[it]==0)
dfs(it);
s.push(node);
}
void dfs2(int node,int k){
visited[node]=-1;
for(auto it:transpus[node])
if(visited[node]>0)
dfs2(it,k);
ctc[k].push_back(node);
}
void da(){
for(int i=1; i<=n; i++)
if(visited[i]==0)
dfs(i);
}
void da2(){
while(!s.empty()){
int v=s.top();
s.pop();
if(visited[v]<0)
continue;
k++;
dfs2(v,k);
}
}
void print(){
fout<<k<<"\n";
for(int i=1; i<=k; i++){
for(auto it:ctc[i])
fout<<it<<" ";
fout<<"\n";
}
}
int main()
{
read();
da();
da2();
print();
return 0;
}