Pagini recente » Cod sursa (job #169219) | Cod sursa (job #2898884) | Cod sursa (job #2135835) | Cod sursa (job #2529543) | Cod sursa (job #2132488)
#include <cstdio>
#include <vector>
#define nmax 100005
using namespace std;
FILE *f=fopen("ctc.in","r");
FILE *g=fopen("ctc.out","w");
vector<int>Q[nmax],Stk,componente[nmax];
int n,m,indexes[nmax],index,lowest[nmax],nrcomponente;
bool instk[nmax];
void read()
{
fscanf(f,"%d %d",&n,&m);
for (int i=1; i<=m; ++i)
{
int a,b;
fscanf(f,"%d %d",&a,&b);
Q[a].push_back(b);
}
}
void tarjan(int nod)
{
indexes[nod]=++index;
lowest[nod]=index;
Stk.push_back(nod);
instk[nod]=true;
for (auto w:Q[nod])
{
if (!indexes[w]) // parcurgem nodurile nevizitate
{
tarjan(w);
lowest[nod]=min(lowest[nod],lowest[w]);
}
else if (instk[w])
{
lowest[nod]=min(lowest[nod],indexes[w]);
// daca e in stack <=> nu face parte dintr-o ctc inca
// e o muchie de intoarcere deci
// altfel, face parte dintr-o ctc deja
}
}
if (lowest[nod]==indexes[nod]) //avem parintele componentei tare conexe
{
int curent;
++nrcomponente;
do
{
curent=Stk.back();
Stk.pop_back();
instk[curent]=false;
componente[nrcomponente].push_back(curent);
}
while (curent!=nod);
}
}
void afis()
{
fprintf(g,"%d\n",nrcomponente);
for (int i=1;i<=nrcomponente;++i)
{for (auto w:componente[i])
fprintf(g,"%d ",w);
fprintf(g,"\n");}
}
void solve()
{
for (int i=1; i<=n; ++i)
if (!indexes[i])
tarjan(i);
}
int main()
{
read();
solve();
afis();
return 0;
}