Pagini recente » Cod sursa (job #1159626) | Cod sursa (job #2363223) | Cod sursa (job #2380004) | Cod sursa (job #752188) | Cod sursa (job #780767)
Cod sursa(job #780767)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define ALB 1
#define GRI 2
#define NEGRU 3
using namespace std;
int n, m;
vector< vector<int> > graph, graphT, solution;
vector<int> c;
stack<int> s;
void dfs(int node)
{
c[node] = GRI;
for(int i = 0; i < graph[node].size(); i++)
{
if(c[graph[node][i]] == ALB)
{
dfs(graph[node][i]);
}
}
s.push(node);
c[node] = NEGRU;
}
void dfsT(int node, int index)
{
solution.resize(index + 1);
solution[index].push_back(node);
c[node] = GRI;
for(int i = 0; i < graphT[node].size(); i++)
{
if(c[graphT[node][i]] == ALB)
{
dfsT(graphT[node][i], index);
}
}
c[node] = NEGRU;
}
void kosaraju()
{
c = vector<int> (n + 1, ALB);
for(int i = 1; i < n + 1; i++)
{
if(c[i] == ALB)
{
dfs(i);
}
}
c = vector<int> (n + 1, ALB);
int i = 0;
while(!s.empty())
{
int node = s.top();
s.pop();
if(c[node] == ALB)
{
dfsT(node, i);
i++;
}
}
}
int main()
{
ifstream in ("ctc.in");
ofstream out ("ctc.out");
int x, y;
in >> n >> m;
graph.resize(n + 1);
graphT.resize(n + 1);
for(int i = 0; i < m; i++)
{
in >> x >> y;
graph[x].push_back(y);
graphT[y].push_back(x);
}
kosaraju();
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;
}