Pagini recente » Cod sursa (job #2958421) | Cod sursa (job #866173) | fara_nume | Cod sursa (job #1359510) | Cod sursa (job #923783)
Cod sursa(job #923783)
//CTC with kosaraju' algorithm
#include<cstdio>
#include<vector>
#include<algorithm>
#include<stack>
#define MAX_N 100005
FILE *f=fopen("ctc.in","r");
FILE *g=fopen("ctc.out","w");
using namespace std;
vector <int> G[MAX_N],GT[MAX_N],sol[MAX_N];
stack <int> S;
int n,m,ctc;
bool used[MAX_N],used_ctc[MAX_N];
void read ( void )
{
fscanf(f,"%d%d",&n,&m);
for(int i(1); i <= m ; ++i )
{
int a,b;
fscanf(f,"%d%d",&a,&b);
G[a].push_back(b);
GT[b].push_back(a);
}
fclose(f);
}
void DFP( int node )
{
vector<int>::iterator it;
used[node]=true;
for(it=G[node].begin(); it!=G[node].end(); ++it)
if(!used[*it])
DFP(*it);
S.push(node);
}
void DFM(int node )
{
vector <int> ::iterator it;
used_ctc[node]=true;
for(it=GT[node].begin(); it!=GT[node].end() ; ++it )
if(!used_ctc[*it])
DFM(*it);
sol[ctc].push_back(node);
}
void solve ( void )
{
for(int i(1); i <= n ; ++i )
if(!used[i])
DFP(i);
while(!S.empty())
{
if(!used_ctc[S.top()])
{
DFM(S.top());
++ctc;
}
S.pop();
}
}
void write( void )
{
vector<int>::iterator it;
fprintf(g,"%d\n",ctc);
for(int i(0); i < ctc; ++i )
{
for(it=sol[i].begin(); it != sol[i].end(); ++it )
{
fprintf(g,"%d ",*it);
}
fprintf(g,"\n");
}
fclose(g);
}
int main( void )
{
read();
solve();
write();
return 0;
}