Pagini recente » Borderou de evaluare (job #1179244) | Cod sursa (job #3139497) | Cod sursa (job #1493481) | Cod sursa (job #1543673) | Cod sursa (job #3199443)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int NMAX=100000;
int N,M,nrc;
vector <int> G[NMAX+1],CTC[NMAX+1];
int D[NMAX+1],Dmin[NMAX+1],Timp=0;
stack<int> S;
bool inSt[NMAX+1];///inSt[i]<==>i este in stiva
ifstream f("ctc.in");
ofstream g("ctc.out");
void citire()
{
int x,y;
f>>N>>M;
for (int i=1;i<=M;i++)
{
f>>x>>y;
G[x].push_back(y);
}
}
void DFS(int x)
{
D[x]=++Timp;
Dmin[x]=D[x];
S.push(x);
inSt[x]=1;
for(auto &y:G[x])
{
if (D[y]==0) ///Muchie de arbore
{
DFS(y);
Dmin[x]=min(Dmin[x],Dmin[y]);
}
else
{
if (inSt[y]==1) ///Muchie de intoarcere
Dmin[x]=min(Dmin[x],D[y]);
///altfel este o muchie inainte sau muchie cross catre alta componenta conexa
}
}
///daca x nu poate urca mai sus de x, atunci el este radacina lui CTC
if (Dmin[x]==D[x]) ///x este radacina unei CTC
{
int u;
nrc++;
do
{
u=S.top();
CTC[nrc].push_back(u);
S.pop();
inSt[u]=0;
}
while(x!=u);
}
}
void afisare()
{
g<<nrc<<'\n';
for (int i=1;i<=nrc;i++)
{
for (auto &x:CTC[i])
g<<x<<' ';
g<<'\n';
}
}
int main()
{
citire();
for (int i=1;i<=N;i++)
{
if (D[i]==0)
DFS(i);
}
afisare();
f.close();
g.close();
}