Pagini recente » Cod sursa (job #667453) | Diferente pentru implica-te/arhiva-educationala intre reviziile 170 si 171 | Cod sursa (job #2395065) | Cod sursa (job #3232520) | Cod sursa (job #2781287)
// parsare preluata de la gabrielinelus
#include <bits/stdc++.h>
#include <fstream>
#define BMAX 500005
#define BU 3666013
#define VMAX 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> adj[VMAX];
stack <int> s;
int V, E, x, y, timp, nr_ctc, w;
bool onStack[VMAX];
int disc[VMAX], low[VMAX];
vector <int> ctc[VMAX];
char Baff[BU];
int pz = BU - 1;
void Read(int &A){
A = 0;
while('0' > Baff[pz] || Baff[pz] > '9')
if(++pz == BU)
fread(Baff,1,BU,stdin),pz = 0;
while('0' <= Baff[pz] && Baff[pz] <= '9')
{
A = (A<<3) + (A<<1) + Baff[pz] - 48;
if(++pz == BU)
fread(Baff,1,BU,stdin),pz = 0;
}
}
void Tarjan(int u)
{
++timp;
disc[u] = timp;
low[u] = timp;
onStack[u] = true;
s.push(u);
for (auto w:adj[u])
{
if (!disc[w]) // elem. nou gasit, (u, v) tree edge
{
Tarjan(w);
// daca componenta aferenta lui v e mai "proaspata", atunci pot sa il bag si pe u in ea, ptc (u, v) e muchie deci pot accesa ac. ctc
low[u] = min(low[u], low[w]);
}
else if (onStack[w]) // daca este pe stack, atunci este unul dintre descendentii lui u
low[u] = min(low[u], disc[w]); // (ex geeksforgeeks) exista cazul in care w este "nodul de trecere" dintre o ctc si alta, deci low[w] ar indica eronat alta comp. conexa
else continue; // altfel, (u, v), este cross edge spre un CTC deja analizat, deci nu facem nimic
}
if (low[u] == disc[u]) // reprez. head node intr un SCC, adica nodul din SCC cu cel mai mic discovery time
{
while (s.top() != u) // cat timp nu ajung la head node
{
x = s.top();
ctc[nr_ctc].push_back(x);
onStack[x] = false;
s.pop();
}
x = s.top();
ctc[nr_ctc].push_back(x);
onStack[x] = false;
s.pop();
++nr_ctc;
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
Read(V);
Read(E);
while (E--)
{
Read(x);
Read(y);
adj[x - 1].push_back(y - 1);
}
for (int u = 0; u < V; ++u)
if (!disc[u]) Tarjan(u);
fout << nr_ctc << endl;
for (int i = 0; i < nr_ctc; ++i)
{
for (int j = 0; j < ctc[i].size(); ++j)
fout << ctc[i][j] + 1 << " ";
fout << endl;
}
fin.close();
fout.close();
return 0;
}