Pagini recente » Cod sursa (job #1889239) | Cod sursa (job #2938606) | Cod sursa (job #1518223) | Cod sursa (job #2877317) | Cod sursa (job #780850)
Cod sursa(job #780850)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define ALB 1
#define GRI 2
#define NEGRU 3
using namespace std;
int n, m, index;
vector< vector<int> > graph, solution;
vector<int> c, idx, lowlink;
stack<int> s;
void tarjan(int node)
{
idx[node] = lowlink[node] = index;
index++;
s.push(node);
c[node] = NEGRU;
for(int i = 0; i < graph[node].size(); i++)
{
if(idx[graph[node][i]] == 0)
{
tarjan(graph[node][i]);
lowlink[node] = min(lowlink[node], lowlink[graph[node][i]]);
}
else
{
if(c[graph[node][i]] == NEGRU)
{
lowlink[node] = min(lowlink[node], idx[graph[node][i]]);
}
}
}
if(lowlink[node] == idx[node])
{
solution.resize(solution.size() + 1);
int tmp;
do
{
tmp = s.top();
s.pop();
solution[solution.size() - 1].push_back(tmp);
} while(tmp != node);
}
}
void ctc_tarjan()
{
index = 0;
c = vector<int> (n + 1, ALB);
idx = vector<int> (n + 1, 0);
lowlink = vector<int> (n + 1, 0);
for(int i = 1; i < n + 1; i++)
{
if(idx[i] == 0)
{
tarjan(i);
}
}
}
int main()
{
ifstream in ("ctc.in");
ofstream out ("ctc.out");
int x, y;
in >> n >> m;
graph.resize(n + 1);
for(int i = 0; i < m; i++)
{
in >> x >> y;
graph[x].push_back(y);
}
ctc_tarjan();
out << solution.size() << '\n';
for(int i = 0; i < solution.size(); i++)
{
for(int j = 0; j < solution[i].size(); j++)
{
out << solution[i][j] << " ";
}
out << '\n';
}
out.close();
in.close();
return 0;
}