Pagini recente » Cod sursa (job #50589) | Cod sursa (job #511431) | Cod sursa (job #1608479) | Cod sursa (job #2350307) | Cod sursa (job #699099)
Cod sursa(job #699099)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
#define nmax 100000
long n, m, k;
bool viz[nmax+1];
vector <long> v[nmax];
vector <long> vt[nmax];
vector <long> cc[nmax];
stack <long> S;
void citire()
{
long x, y;
freopen("ctc.out", "w", stdout); freopen("ctc.in", "r", stdin);
scanf("%ld %ld", &n, &m);
for(long i=1; i<=m; i++)
{
scanf("%ld %ld", &x, &y);
v[x].push_back(y);
vt[y].push_back(x);
}
}
void afisare()
{
printf("%ld \n", k);
for(long i=1; i<=k; i++)
{
for(long j=0; j<cc[i].size(); j++)
printf("%ld ", cc[i][j]);
printf("\n");
}
}
void dfst(int nod)
{
viz[nod] = false; cc[k].push_back(nod);
for(long i=0; i<vt[nod].size(); i++)
if( viz[ vt[nod][i] ] == true)
dfst( vt[nod][i] );
}
void dfs(int nod)
{
viz[nod] = true;
for(long i=0; i<v[nod].size(); i++)
if( viz[ v[nod][i] ] == false )
dfs( v[nod][i] );
S.push(nod);
}
void kosaraju()
{
for(long i=1; i<=n; i++)
if( viz[i] == false )
dfs(i);
while( !S.empty() )
{
if( viz[ S.top() ] == true)
{
k++;
dfst(S.top());
}
S.pop();
}
}
int main()
{
citire();
kosaraju();
afisare();
return 0;
}