Pagini recente » Cod sursa (job #883986) | Cod sursa (job #797956) | Cod sursa (job #2842379) | Cod sursa (job #1477918) | Cod sursa (job #903114)
Cod sursa(job #903114)
#include<cstdio>
#include<fstream>
#include<vector>
#include<set>
#define MAX 100005
#define pb push_back
using namespace std;
int N ,M , nr , tf[MAX] , fin , l[MAX] , sol[MAX] , pas , k;
bool viz[MAX];
vector<int> G[MAX] , GT[MAX];
struct cmp{bool operator()(int x , int y){return tf[x] > tf[y];}};
multiset<int,cmp> Q;
void citire();
void solve();
void DF(int nod);
void DFT(int nod);
void tipar();
int main()
{
citire();
solve();
tipar();
return 0;
}
void citire()
{
int x , y;
ifstream f("ctc.in");
f>>N>>M;
for(int i = 1 ; i <= M ; ++i )
{
f>>x>>y;
G[x].pb(y);
GT[y].pb(x);
}
f.close();
}
void solve()
{
for( int i = 1 ; i <= N ; ++i )
if(!viz[i])DF(i);
for(int i = 1 ; i <= N ; ++i )Q.insert(i);
for(int i = 1 ; i <=N ; ++i )viz[i] = 0;
while(!Q.empty())
{
if(viz[*Q.begin()])
Q.erase(Q.begin());
else
{
DFT(*Q.begin());
sol[++sol[0]] = k;
}
}
}
void DF(int nod)
{
pas++;
viz[nod] = 1;
for( int i = 0 ; i < G[nod].size() ; ++i )
if(!viz[G[nod][i]])
DF(G[nod][i]),pas++;
tf[nod] = pas;
}
void DFT(int nod)
{
viz[nod] = 1;
for(int i = 0 ; i < GT[nod].size() ; ++i )
if(!viz[GT[nod][i]])
DFT(GT[nod][i]);
l[++k] = nod;
}
void tipar()
{
ofstream g("ctc.out");
g<<sol[0]<<"\n";
for(int i = 1 ; i <= sol[0] ; ++i )
{
int j;
for(j = (i==1 )? 1 : sol[i-1] + 1 ; j <= sol[i] ; ++j )
g<<l[j]<<" ";
g<<"\n";
}
/*for( int i = 1 ; i <= N ; ++i)
{
for(int j = 0 ; j < GT[i].size() ; ++j )
g<<GT[i][j]<<" ";
g<<"\n";
}*/
g.close();
}