Pagini recente » Cod sursa (job #944849) | Cod sursa (job #423827)
Cod sursa(job #423827)
#include <fstream>
#include <stack>
#include <vector>
#define MAXN 100005
#define Min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector <int> adj[MAXN], con, idx, lowlink, in_stack;
vector < vector <int> > C;
stack <int> S;
int indecs;
void tarjan(const int n, const vector <int>* adj)
{
idx[n] = lowlink[n] = indecs;
indecs ++;
S.push(n), in_stack[n] = 1;
vector <int>::const_iterator it;
for (it = adj[n].begin(); it != adj[n].end(); ++ it) {
if (idx[*it] == -1)
tarjan(*it, adj), lowlink[n] = Min(lowlink[n], lowlink[*it]);
else if (in_stack[*it]) lowlink[n] = Min(lowlink[n], lowlink[*it]);
}
if (idx[n] == lowlink[n])
{
con.clear();
int node;
do
{
con.push_back(node = S.top());
S.pop(), in_stack[node] = 0;
}
while (node != n);
C.push_back(con);
}
}
int main()
{
int n;
int cnt_edges, x, y;
in >> n;
for (in >> cnt_edges; cnt_edges > 0; -- cnt_edges)
in >> x >> y, adj[x - 1].push_back(y - 1);
in.close();
idx.resize(n), lowlink.resize(n), in_stack.resize(n);
idx.assign(n, -1), in_stack.assign(n, 0);
for (int i = 0; i < n; ++ i)
if (idx[i] == -1) tarjan(i, adj);
out << C.size() << "\n";
for (size_t i = 0; i < C.size(); ++ i)
{
for (size_t j = 0; j < C[i].size(); ++ j) out << C[i][j] + 1 << " ";
out << "\n";
}
return 0;
}