Pagini recente » Cod sursa (job #1842774) | Cod sursa (job #2860522) | Cod sursa (job #2126186) | Cod sursa (job #1080464) | Cod sursa (job #1491300)
#include <fstream>
#include <vector>
#define maxn 100001
#define vint vector<int>::iterator
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
vector<int> G[maxn],CC[maxn];
int lowlink[maxn],index[maxn],current,stack[maxn],n,m,a,b,t,nr;
bool is_in_stack[maxn];
void Tarjan (int x)
{
index[x] = ++current;
lowlink[x] = index[x];
is_in_stack[x] = 1;
stack [++t] = x;
for (vint it = G[x].begin(); it != G[x].end(); ++it)
{
if (!index[*it])
{
Tarjan (*it);
lowlink[x] = min (lowlink[x],lowlink[*it]);
}
else if (is_in_stack[*it])
{
lowlink[x] = min (lowlink[x],lowlink[*it]);
}
}
if (lowlink[x] == index[x])
{
++nr;
while ( stack[t] != x)
{
CC[nr].push_back (stack[t]);
is_in_stack[stack[t]] = 0;
--t;
}
CC[nr].push_back (x);
is_in_stack[x] = 0;
--t;
}
}
int main()
{
fin>>n>>m;
for (int i=1; i<=m; ++i)
{
fin>>a>>b;
G[a].push_back (b);
}
for (int i=1; i<=n; ++i)
{
if (!index[i]) Tarjan(i);
}
fout<<nr<<"\n";
for (int i=1; i<=nr; ++i)
{
for (vint it = CC[i].begin(); it != CC[i].end(); ++it)
{
fout<<*it<<" ";
}
fout<<"\n";
}
}