Pagini recente » Cod sursa (job #22950) | Cod sursa (job #973819)
Cod sursa(job #973819)
#include <fstream>
#include <vector>
#define maxn 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> G[maxn],CC[maxn];
int stack[maxn],order[maxn],lowest_in[maxn],visited[maxn],is_in_stack[maxn];
int n,m,lvl,current,nr,a,b;
void Tarjan (int x)
{
visited[x]=1;
order[x]=++current;
lowest_in[x]=order[x];
is_in_stack[x]=1;
stack[++lvl]=x;
for (vector<int>::iterator it=G[x].begin(); it!=G[x].end(); ++it)
{
if (!visited[*it])
{
Tarjan (*it);
lowest_in[x] = min (lowest_in[x],lowest_in[*it]);
}
else if (is_in_stack[*it])
lowest_in[x] = min (lowest_in[x],order[*it]);
}
if (order[x]==lowest_in[x])
{
++nr;
while (stack[lvl]!=x)
{
CC[nr].push_back(stack[lvl]);
is_in_stack[stack[lvl]]=0;
lvl--;
}
CC[nr].push_back (x);
is_in_stack[x]=0;
lvl--;
}
}
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 (!visited[i]) Tarjan (i);
}
fout<<nr<<"\n";
for (int i=1; i<=nr; i++)
{
for (vector<int>::iterator it=CC[i].begin(); it!=CC[i].end(); ++it)
fout<<*it<<" ";
fout<<"\n";
}
}