Pagini recente » Cod sursa (job #1115234) | Cod sursa (job #291803) | Cod sursa (job #2838773) | Cod sursa (job #2683102) | Cod sursa (job #1795412)
//complxitate O(n+m)
#include <fstream>
#include<vector>
#include<stack>
#include<algorithm>
#define Nmax 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n;
bool vg[Nmax],vgt[Nmax];
vector <int> g[Nmax],gt[Nmax],c[Nmax];
stack <int> s;
void citeste(){
int m,x,y;
fin>>n>>m;
for(int i=1;i<=m;i++){
fin>>x>>y;
g[x].push_back(y);
gt[y].push_back(x);
}
}
void dfs1(int x){
vg[x]=1;
for(unsigned int i=0;i<g[x].size();i++)
if(vg[g[x][i]]==0){
dfs1(g[x][i]);
}
s.push(x);
}
void dfs2(int x,int nr){
vgt[x]=1;
c[nr].push_back(x);
for(unsigned int i=0;i<gt[x].size();i++)
if(vgt[gt[x][i]]==0){
dfs2(gt[x][i],nr);
}
}
int main()
{
int i,nr=0;
citeste();
for(i=1;i<=n;i++)
if(vg[i]==0){
dfs1(i);
}
while(!s.empty()){
i=s.top();
s.pop();
if(vgt[i]==0){
dfs2(i,nr);
nr++;
}
}
fout<<nr<<"\n";
for(i=0;i<nr;i++){
sort(c[i].begin(),c[i].end());
for(unsigned int j=0;j<c[i].size();j++)
fout<<c[i][j]<<" ";
fout<<"\n";
}
return 0;
}