Pagini recente » Cod sursa (job #285162) | Cod sursa (job #2519390) | Cod sursa (job #1725424) | Cod sursa (job #3183229) | Cod sursa (job #754883)
Cod sursa(job #754883)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
vector<int> *Muchii;
stack<int> S;
long Time;
long Out[200010];
long Outp;
long D[100005];
long Low[100005];
long Count;
long N,M;
void tarjan(long p)
{
long a,b,c;
D[p] = Time;
Low[p] = Time;
Time += 1;
S.push(p);
for (a = 0;a < Muchii[p].size();a += 1)
{
b = Muchii[p][a];
if (D[b] == 0)
{
tarjan(b);
if (Low[b] < Low[p])
{
Low[p] = Low[b];
}
}
else
{
if (D[b] < Low[p])
{
Low[p] = D[b];
}
}
}
if (Low[p] == D[p])
{
Count += 1;
while (S.top() != p)
{
Out[Outp] = S.top();
Outp += 1;
S.pop();
}
Out[Outp] = S.top();
Outp += 1;
S.pop();
Out[Outp] = 0;
Outp += 1;
}
}
int main(void)
{
long i,a,b;
fstream fin("ctc.in",ios::in);
fstream fout("ctc.out",ios::out);
fin >> N >> M;
Muchii = new vector<int>[N + 5];
for (i = 0;i < N;i += 1)
{
Muchii[i].reserve(20);
}
for (i = 0;i < M;i += 1)
{
fin >> a >> b;
Muchii[a].push_back(b);
}
Time = 1;
for (i = 1;i <= N;i += 1)
{
if (D[i] == 0)
{
tarjan(i);
}
}
fout << Count << "\n";
for (i = 0;i < Outp;i += 1)
{
if (Out[i] == 0)
{
fout << "\n";
}
else
{
fout << Out[i] << " ";
}
}
fin.close();
fout.close();
return 0;
}