Pagini recente » Cod sursa (job #212701) | Cod sursa (job #315484) | Cod sursa (job #2633083) | Cod sursa (job #743204) | Cod sursa (job #1021985)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
#define DN 100005
#define pb push_back
using namespace std;
vector<int> list[DN],tmp,tr[DN];
vector< vector<int> > rez;
bitset<DN> viz;
int stiva[DN];
void dfs(int nod)
{
viz[nod]=true;
for(int i=0;i<list[nod].size();++i){
int next_nod=list[nod][i];
if(!viz[next_nod])
dfs(next_nod);
}
stiva[++stiva[0]]=nod;
}
void dfs2(int nod)
{
viz[nod]=true;
tmp.push_back(nod);
for(int i=0;i<tr[nod].size();++i){
int next_nod=tr[nod][i];
if(!viz[next_nod])
dfs2(next_nod);
}
}
int main()
{
int n,m;
ifstream f("ctc.in");
ofstream g("ctc.out");
f>>n>>m;
for(;m;--m)
{
int a,b;
f>>a>>b;
list[a].pb(b);
tr[b].pb(a);
}
for(int i=1;i<=n;++i)
if(!viz[i])
dfs(i);
viz&=0;
while(stiva[0]){
tmp.clear();
int nod=stiva[stiva[0]];
if(!viz[nod]){
dfs2(nod);
rez.pb(tmp);
}
--stiva[0];
}
g<<rez.size()<<"\n";
for(int i=0;i<rez.size();++i,g<<"\n")
for(int j=0;j<rez[i].size();++j)
g<<rez[i][j]<<" ";
return 0;
}