Pagini recente » Cod sursa (job #1429681) | Cod sursa (job #111016) | Cod sursa (job #3288305) | Cod sursa (job #2522516) | Cod sursa (job #1727817)
#include <fstream>
#include <vector>
#include <stack>
#define inf 1<<30
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> G[100001];
struct desprenod
{
int nr,pred,ok;
}car[100001];
vector <vector <int>> ctc;
vector <int> comp;
stack <int> St;
int pas,n,m,i,j,k,ok,x,y,l=0;
void tarjan (int nod)
{
int v,i; //declara i-ul asta nenorocit local, ca altfel te ia dracu
car[nod].nr=pas;
car[nod].pred=pas;
car[nod].ok=1;
St.push(nod);
pas++;
for(i=0;i<G[nod].size();i++)
{
v=G[nod][i];
if(car[v].nr==inf)
{
tarjan(v);
car[nod].pred=min(car[nod].pred,car[v].pred);
}
else if(car[v].ok==1)
car[nod].pred=min(car[nod].pred,car[v].nr);
}
if(car[nod].nr==car[nod].pred)
{
comp.clear();
do
{
v=St.top();
St.pop();
car[v].ok=0;
comp.push_back(v);
}while (v!=nod) ;
ctc.push_back(comp);
}
}
int main()
{
f>>n>>m;
for(i=1;i<=n;i++) car[i].nr=inf;
for(i=1;i<=m;i++)
{
f>>x>>y;
G[x].push_back(y);
}
pas=1;
for(i=1;i<=n;i++)
if(car[i].nr==inf)
tarjan(i);
g<<ctc.size()<<'\n';
for(i=0;i<ctc.size();i++)
{
for(j=0;j<ctc[i].size();j++) g<<ctc[i][j]<<' ';
g<<'\n';
}
return 0;
}