Pagini recente » Diferente pentru implica-te/arhiva-educationala intre reviziile 206 si 223 | Cod sursa (job #3292331) | Cod sursa (job #3286793) | Istoria paginii implica-te/arhiva-educationala | Cod sursa (job #3286870)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, m;
vector<int> v[100005], idx, lowlink, in_stack;
vector<vector<int>> C; // SCC storage
stack<int> S;
int indecs = 0;
void tarjan(int x)
{
idx[x] = lowlink[x] = ++indecs;
S.push(x);
in_stack[x] = 1;
for (auto y: v[x])
{
if (idx[y] == 0)
{
tarjan(y);
lowlink[x] = min(lowlink[x], lowlink[y]);
}
else if (in_stack[y])
{
lowlink[x] = min(lowlink[x], idx[y]);
}
}
if (idx[x] == lowlink[x])
{
vector<int> con;
int node;
do
{
node = S.top();
S.pop();
in_stack[node] = 0;
con.push_back(node);
} while (node != x);
C.push_back(con);
}
}
int main()
{
cin >> n >> m;
// Read input graph (1-based indexing)
for (int i = 0; i < m; ++i)
{
int x, y;
cin >> x >> y;
v[x].push_back(y);
}
// Initialize arrays
idx.resize(n + 1, 0);
lowlink.resize(n + 1);
in_stack.resize(n + 1, 0);
// Run Tarjan's algorithm
for (int i = 1; i <= n; ++i)
{
if (!idx[i])
{
tarjan(i);
}
}
for(int i = 0; i < C.size(); ++i)
{
reverse(C[i].begin(), C[i].end());
}
// Print SCCs
cout << C.size() << "\n";
for (int i = 0; i < C.size(); ++i)
{
for (int j = 0; j < C[i].size(); ++j)
{
cout << C[i][j] << ' ';
}
cout << '\n';
}
return 0;
}