Pagini recente » Cod sursa (job #16431) | Cod sursa (job #1881395) | Cod sursa (job #1198759) | Cod sursa (job #3192786) | Cod sursa (job #2901930)
#include <fstream>
#include <vector>
//tarjan
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
#define pauza 999999
vector <int> v[100005];
int viz[100005], low[100005], stiva[100005], afis[200005];
int t, nr_comp, nr;
void dfs(int start, int lv)
{
viz[start] = 2;
low[start] = lv;
t++;
stiva[t] = start;
for(int i=0; i<v[start].size(); i++)
{
int vecin = v[start][i];
if(viz[vecin] == 0)
dfs(vecin, lv+1);
if(viz[vecin] == 2)
low[start] = min(low[start], low[vecin]);
}
if(lv == low[start])
{
nr_comp++;
do
{
viz[stiva[t]] = 1;
nr++;
afis[nr] = stiva[t];
t--;
}while(stiva[t+1] != start);
nr++;
afis[nr] = pauza;
}
}
int main()
{
int n,m,i,a,b;
f>>n>>m;
for(i=1; i<=m; i++)
{
f>>a>>b;
v[a].push_back(b);
}
for(i=1; i<=n; i++)
if(viz[i] == 0)
dfs(i, 1);
g<<nr_comp<<'\n';
nr = 1;
for(i=1; i<=nr_comp; i++)
{
while(afis[nr] != pauza)
{
g<<afis[nr]<<' ';
nr++;
}
g<<'\n';
nr++;
}
return 0;
}