Pagini recente » Cod sursa (job #2690717) | Cod sursa (job #1330192) | Cod sursa (job #1887852) | Cod sursa (job #2847764) | Cod sursa (job #1961364)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
struct Nod
{
int index, lowlink;
bool onStack;
};
int g, N, M, i, j, index, x, y;
stack<int> S;
vector<int> e[100003];
vector<int> sct[100003];
Nod n[100003];
void strongConnect(int v)
{
int w, si;
++index;
n[v].index = index;
n[v].lowlink = index;
S.push(v);
n[v].onStack = true;
for(si = 0; si < e[v].size(); ++si)
{
w = e[v][si];
if(n[w].index == 0)
{
strongConnect(w);
n[v].lowlink = min(n[w].lowlink, n[v].lowlink);
}
else if(n[w].onStack)
{
n[v].lowlink = min(n[w].lowlink, n[v].lowlink);
}
}
if(n[v].index == n[v].lowlink)
{
do
{
w = S.top();
S.pop();
n[w].onStack = false;
sct[g].push_back(w);
}
while(v != w);
++g;
}
}
int main()
{
fin>>N>>M;
for(i = 0; i < M; ++i)
{
fin>>x>>y;
e[x].push_back(y);
}
for(i = 1; i <= N; ++i)
{
if(n[i].index == 0)
{
strongConnect(i);
}
}
fout<<g<<'\n';
for(i = 0; i < g; ++i)
{
for(j = 0; j < sct[i].size(); ++j)
{
fout<<sct[i][j]<<" ";
}
fout<<'\n';
}
return 0;
}