Pagini recente » Cod sursa (job #1044475) | Cod sursa (job #1806569) | Cod sursa (job #2842734) | Cod sursa (job #2030365) | Cod sursa (job #3216676)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int MAXN = 300000;
int N, M;
vector<int> G[MAXN + 1];
bitset<MAXN + 1> viz;
int idx[MAXN + 1], ll[MAXN + 1];
stack<int> tStack;
bitset<MAXN + 1> inTStack;
int gIdx = 0;
vector<vector<int>> comps;
void read()
{
fin >> N >> M;
int a, b;
while (M--)
{
fin >> a >> b;
G[a].emplace_back(b);
}
}
void tarjan(int nod)
{
tStack.emplace(nod);
inTStack[nod] = 1;
viz[nod] = 1;
idx[nod] = ll[nod] = ++gIdx;
for (const auto &x : G[nod])
{
if (!viz[x])
{ // tree edge
tarjan(x);
ll[nod] = min(ll[nod], ll[x]);
}
else if (inTStack[x])
{ // back edge
ll[nod] = min(ll[nod], idx[x]);
}
}
if (ll[nod] == idx[nod])
{
// extract ctc
int ex;
vector<int> comp;
do
{
ex = tStack.top();
tStack.pop();
inTStack[ex] = 0;
comp.emplace_back(ex);
} while (ex != nod);
comps.emplace_back(comp);
}
}
void make_ctc()
{
for (int i = 1; i <= N; ++i)
{
if (!viz[i])
tarjan(i);
}
}
void print() {
fout << comps.size() << '\n';
for(const auto& comp : comps) {
for(const auto& x : comp) {
fout << x << ' ';
}
fout << '\n';
}
}
int main()
{
read();
make_ctc();
print();
return 0;
}