Pagini recente » Cod sursa (job #1689473) | Cod sursa (job #216156) | Cod sursa (job #1588782) | Cod sursa (job #1000318) | Cod sursa (job #1366515)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n, m, nr, w, modul, lowlink[100001], index[100001], vf[200001], urm[200001], lst[100001];
vector <int> noduri, radacini;
stack <int> st;
bool viz[100001], removed[100001];
int minim(int x, int y)
{
if(y<x) return y;
return x;
}
void strongconnect(int x)
{
int p, y;
viz[x]=true;
index[x]=nr;
lowlink[x]=nr;
nr++;
st.push(x);
removed[x]=false;
p=lst[x];
while(p!=0)
{
y=vf[p];
if(!viz[y])
{
strongconnect(y);
lowlink[x]=minim(lowlink[x], lowlink[y]);
}
else if(!removed[y]) lowlink[x]=minim(lowlink[x], index[y]);
p=urm[p];
}
if(lowlink[x]==index[x] && st.top()!=x)
{
w++;
do
{
y=st.top();
st.pop();
noduri.push_back(y);
modul++;
removed[y]=true;
}while(x!=y);
radacini.push_back(modul);
}
nr--;
}
int main()
{
int i, j=0, x, y;
in>>n>>m;
for(i=1;i<=m;i++)
{
in>>x>>y;
vf[i]=y;
urm[i]=lst[x];
lst[x]=i;
lowlink[i]=100001;
index[i]=100001;
}
for(i=1;i<=n;i++)
{
if(!viz[i]) strongconnect(i);
}
out<<w<<"\n";
for(i=0;i<=modul-1;i++)
{
out<<noduri[i]<<" ";
if(radacini[j]==i+1)
{
j++;
out<<"\n";
}
}
return 0;
}