Pagini recente » Monitorul de evaluare | Cod sursa (job #2264051) | Cod sursa (job #1244427) | Cod sursa (job #1033662) | Cod sursa (job #703738)
Cod sursa(job #703738)
#include <fstream>
#include <vector>
using namespace std;
int N, M;
vector<int> V[100002];
int W[100002], Wnow[100002];
int ST[100002];
vector<vector<int> > R;
void Tarjan(int x)
{
ST[++ST[0]] = x;
W[x] = ++W[0];
Wnow[x] = W[0];
for (vector<int>::iterator it = V[x].begin(); it != V[x].end(); ++it)
{
if (!W[*it])
Tarjan(*it);
Wnow[x] = min(Wnow[x], Wnow[*it]);
}
if (W[x] == Wnow[x])
{
R.push_back(vector<int>());
while (ST[ST[0]] != x)
{
R.back().push_back(ST[ST[0]]);
--ST[0];
}
R.back().push_back(x);
--ST[0];
}
}
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
fin >> N >> M;
for (int i = 1, nod1, nod2; i <= M; ++i)
{
fin >> nod1 >> nod2;
V[nod1].push_back(nod2);
}
for (int i = 1; i <= N; ++i)
if (!W[i])
Tarjan(i);
fout << R.size() << '\n';
for (int i = 0; i < R.size(); ++i)
{
for (vector<int>::iterator it = R[i].begin(); it != R[i].end(); ++it)
fout << *it << ' ';
fout << '\n';
}
fin.close();
fout.close();
}