Pagini recente » Cod sursa (job #2764160) | Cod sursa (job #32816) | Cod sursa (job #1959515) | Cod sursa (job #964838) | Cod sursa (job #531305)
Cod sursa(job #531305)
#include<fstream>
#include<vector>
#include<stack>
#include<iterator>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
# define nmax 100002
# define min(a,b) ((a<b)? (a):(b))
vector <int> v[nmax],ctc;
vector <vector <int> > afis;
stack <int> S;
int N,M,idx[nmax],lowlink[nmax],index;
bool inS[nmax];
void citire()
{
f>>N>>M;
int i,j;
for(;M;--M)
f>>i>>j, v[i].push_back(j);
}
void tarzan(int nod)
{
++index;
idx[nod]=lowlink[nod]=index;
S.push(nod), inS[nod]=1;
vector <int>::const_iterator it;
for(it=v[nod].begin();it!=v[nod].end();++it)
if(!idx[*it])
tarzan(*it),
lowlink[nod]=min(lowlink[nod], lowlink[*it]);
else if(inS[*it])
lowlink[nod]=min(lowlink[nod], lowlink[*it]);
if(idx[nod]==lowlink[nod])
{
int bla;
ctc.clear();
do{
bla=S.top();
S.pop(), inS[bla]=0;
ctc.push_back(bla);
}while(bla!=nod);
afis.push_back(ctc);
}
}
void afisare()
{
int n,m,i,j;
n=afis.size();
g<<n<<'\n';
for(i=0;i<n;++i)
{
m=afis[i].size();
for(j=0;j<m;++j)
g<<afis[i][j]<<' ';
g<<'\n';
}
}
int main()
{
citire();
int i;
for(i=1;i<=N;++i)
if(!idx[i]) tarzan(i);
afisare();
}