Pagini recente » Cod sursa (job #2913188) | Cod sursa (job #611836) | Cod sursa (job #2182683) | Cod sursa (job #1228260) | Cod sursa (job #1923646)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 100005
ifstream f{ "ctc.in" };
ofstream q{ "ctc.out" };
vector<int> graph[NMAX];
vector<int> stack;
vector< vector<int> >sol;
int visited[NMAX], lowLink[NMAX];
bool onStack[NMAX];
int index = 1;
int n, m;
void read()
{
int x, y;
f >> n >> m;
for(int i = 0; i < m; ++i)
{
f >> x >> y;
graph[x].push_back(y);
}
}
void printComponent()
{
q << sol.size() << "\n";
for(auto& comp : sol)
{
for (auto& c : comp) q << c << " ";
q << "\n";
}
}
void tarjan(int node)
{
visited[node] = index;
lowLink[node] = index;
onStack[node] = true;
stack.push_back(node);
index++;
for(auto vec : graph[node])
{
if (visited[vec] == 0)
{
tarjan(vec);
lowLink[node] = min(lowLink[node], lowLink[vec]);
}
else if (onStack[vec])
{
lowLink[node] = min(lowLink[node], lowLink[vec]);
}
}
if (lowLink[node] == visited[node])
{
vector<int> currentComponent;
int c;
do
{
c = stack.back();
currentComponent.push_back(c);
stack.pop_back();
onStack[c] = false;
} while (c != node);
sol.push_back(currentComponent);
}
}
int main()
{
read();
for(int i = 1; i<=n; ++i)
{
if (visited[i] == 0) tarjan(i);
}
printComponent();
f.close();
q.close();
return 0;
}