Pagini recente » Cod sursa (job #312991) | Cod sursa (job #692432) | Cod sursa (job #1529622) | Cod sursa (job #1161770) | Cod sursa (job #530727)
Cod sursa(job #530727)
#include <fstream>
#include <vector>
#include <utility>
#include <stack>
using namespace std;
struct vertex
{
vertex()
{
x = y = i = m = f;
}
int x, y, i, m, f;
};
vector<vertex> G(200001);
vector<int> V(200001, 0);
vector<int> D;
stack<int> P, S;
int idx, C = 0, N, M;
void tarjan(int i);
int main()
{
ifstream in("ctc.in");
ofstream out("ctc.out");
in >> N >> M;
for (int i = 1; i <= M; i++)
in >> G[i].x >> G[i].y;
for (int i = 1; i <= M; i++)
if (G[i].i)
tarjan(i);
out << D.size() << '\n';
for (int i = 0; i <= (int) D.size(); i++)
out << G[i].x << ' ' << G[i].y;
}
void tarjan(int i)
{
G[i].i = idx;
G[i].m = idx;
idx++;
S.push(i);
G[i].f = 1;
int j = 1, k = 1;
for (; j <= M; j++)
{
for (; k <= M; k++)
{
if (!G[k].i)
{
tarjan(k);
G[j].m = min(G[j].m, G[k].m);
}
else if (G[k].f)
{
G[j].m = min(G[j].m, G[k].i);
}
}
}
if (G[j].m == G[k].m)
{
do
{
k = S.top();
S.pop();
D.push_back(k);
} while (i != k);
}
}