Pagini recente » Cod sursa (job #129012) | Cod sursa (job #269150) | Cod sursa (job #2029830) | Cod sursa (job #2897246) | Cod sursa (job #2896667)
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[100005], con, idx, lowlink, in_stack;
vector<vector<int>> C;
stack<int> S;
int indecs;
void citire(vector<int> *adj, int & n)
{
ifstream fin("ctc.in");
int m, x, y;
fin >> n >> m;
while(m)
{
fin >> x >> y;
adj[x - 1].push_back(y - 1);
m--;
}
}
void afisare(vector<vector<int>> G)
{
ofstream fout("ctc.out");
fout << G.size() << "\n";
for (size_t i = 0; i < G.size(); ++ i) {
for (size_t j = 0; j < G[i].size(); ++ j)
fout << G[i][j] + 1 << " ";
fout << '\n';
}
}
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;
citire(adj, n);
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);
afisare(C);
return 0;
}