Pagini recente » Cod sursa (job #1732873) | Cod sursa (job #473289) | Cod sursa (job #1540272) | Cod sursa (job #183015) | Cod sursa (job #530732)
Cod sursa(job #530732)
#include <fstream>
#include <vector>
#include <utility>
#include <stack>
using namespace std;
struct vertex
{
vertex()
{
x = y = i = m = f = 0;
}
int x, y, i, m, f;
};
vector<vertex> G(200001);
vector<int> V(200001, 0);
vector<int> D;
stack<int> 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 << C << '\n';
for (int i = 0; i <= (int) D.size(); i++)
out << G[i].x << ' ' << G[i].y << '\n';
}
void tarjan(int i)
{
G[i].i = idx;
G[i].m = idx;
idx++;
S.push(i);
G[i].f = 1;
int j = i;
for (; j <= M; j++)
{
if (!G[j].i)
{
tarjan(j);
G[i].m = min(G[i].m, G[j].m);
}
else if (G[j].f)
{
G[i].m = min(G[i].m, G[j].i);
}
}
if (G[i].m == G[j].m)
{
C++;
do
{
j = S.top();
S.pop();
D.push_back(j);
} while (i != j);
}
}