Pagini recente » Cod sursa (job #1837179) | Cod sursa (job #1592298) | Cod sursa (job #1170761) | Cod sursa (job #723150) | Cod sursa (job #493347)
Cod sursa(job #493347)
#include <fstream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#define NMAX 100001
using namespace std;
vector<int> C[NMAX],G[NMAX];
stack<int> S;
int V[NMAX];
int N,M;
int K;
bool viz[NMAX];
queue<int> Q;
int NR;
vector<int>CTC[NMAX];
inline void citire()
{
fstream fin("ctc.in",ios::in);
fin>>N;
fin>>M;
int x,y;
for(int i=1;i<=M;i++)
{
fin>>x>>y;
G[x].push_back(y);
C[y].push_back(x);
}
fin.close();
}
inline void afisare()
{
fstream fout("ctc.out",ios::out);
fout<<NR<<"\n";
for(int i=1;i<=NR;i++)
{
for(unsigned int j=0;j<CTC[i].size();j++)
fout<<CTC[i][j]<<" ";
fout<<"\n";
}
fout.close();
}
void DFS(int x)
{
viz[x]=true;
for(unsigned int i=0;i<G[x].size();i++)
{
if(!viz[G[x][i]])
DFS(G[x][i]);
}
V[K--]=x;
}
void DF()
{
int x;
while(!S.empty())
{
x=S.top();
viz[x]=true;
S.pop();
Q.push(x);
for(unsigned int i=0;i<C[x].size();i++)
{
if(!viz[C[x][i]])
S.push(C[x][i]);
}
}
}
int main(int argc, char*argv[])
{
citire();
K=N;
for(int i=1;i<=N;i++)
if(!viz[i])
DFS(i);
memset(viz,false,sizeof(viz));
for(int i=1;i<=N;i++)
{
if(!viz[V[i]])
{
S.push(V[i]);
DF();
if(Q.size()>0)
NR++;
while(!Q.empty())
{
CTC[NR].push_back(Q.front());
Q.pop();
}
}
}
afisare();
}