Pagini recente » Cod sursa (job #641896) | Cod sursa (job #1789298) | Cod sursa (job #1787902) | Cod sursa (job #2398492) | Cod sursa (job #801013)
Cod sursa(job #801013)
#include <fstream>
#include <vector>
using namespace std;
const char InFile[]="ctc.in";
const char OutFile[]="ctc.out";
const int MaxN=100111;
ifstream fin(InFile);
ofstream fout(OutFile);
int N,M,x,y,viz[MaxN],S[MaxN];
vector<int> G[MaxN],GT[MaxN],c;
vector< vector<int> > C;
void DFP(int nod)
{
viz[nod]=1;
for(vector<int>::iterator it=G[nod].begin();it!=G[nod].end();++it)
{
if(!viz[*it])
{
DFP(*it);
}
}
S[++S[0]]=nod;
}
void DFM(int nod)
{
c.push_back(nod);
viz[nod]=0;
for(vector<int>::iterator it=GT[nod].begin();it!=GT[nod].end();++it)
{
if(viz[*it])
{
DFM(*it);
}
}
}
inline void Kosaraju()
{
for(register int i=1;i<=N;++i)
{
if(!viz[i])
{
DFP(i);
}
}
while(S[0])
{
int x=S[S[0]];
if(viz[x])
{
c.clear();
DFM(x);
C.push_back(c);
}
--S[0];
}
}
int main()
{
fin>>N>>M;
for(register int i=1;i<=M;++i)
{
fin>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
fin.close();
Kosaraju();
fout<<C.size()<<"\n";
for(vector< vector<int> >::iterator it=C.begin();it!=C.end();++it)
{
for(vector<int>::iterator it2=it->begin();it2!=it->end();++it2)
{
fout<<*it2<<" ";
}
fout<<"\n";
}
fout.close();
return 0;
}