Pagini recente » Arhiva de probleme | Istoria paginii runda/simulare-oni-2019-cls10-ziua1 | Cod sursa (job #176397) | Cod sursa (job #1818081) | Cod sursa (job #1857069)
#include <fstream>
#include <vector>
#define nMax 100001
#define pb push_back
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, index, nrctc;
int lev[nMax], low[nMax];
bool viz[nMax];
vector<int> G[nMax];
vector<int> ctc[nMax];
vector<int> stck;
void tarjan(int node)
{
viz[node]=1;
stck.pb(node);
lev[node]=low[node]=++index;
for(vector<int>::iterator it=G[node].begin(); it!=G[node].end(); it++)
{
int fiu=*it;
if(lev[fiu]==0)
{
tarjan(fiu);
low[node]=min(low[node], low[fiu]);
}
else
{
if(viz[fiu]==1)
low[node]=min(low[node], low[fiu]);
}
}
if(lev[node]==low[node])
{
nrctc++;
int papa;
do
{
papa=stck.back();
stck.pop_back();
viz[papa]=0;
ctc[nrctc].pb(papa);
}
while(papa!=node);
}
}
int main()
{
int a, b;
fin>>n>>m;
for(int i=1; i<=m; i++)
{
fin>>a>>b;
G[a].pb(b);
}
for(int i=1; i<=n; i++)
if(lev[i]==0)
tarjan(i);
fout<<nrctc<<'\n';
for(int i=1; i<=nrctc; i++)
{
for(vector<int>::iterator it=ctc[i].begin(); it!=ctc[i].end(); it++)
fout<<*it<<" ";
fout<<'\n';
}
}