Pagini recente » Cod sursa (job #1262767) | Cod sursa (job #1887518) | Cod sursa (job #1825763) | Cod sursa (job #2390016) | Cod sursa (job #2128132)
#include <cstdio>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;
const int NMAX = 100010;
vector <int> graf[NMAX];
int n,m,index[NMAX],lowlink[NMAX],valinitiala,componente;
stack <int> stiva;
vector<int> solutie[NMAX];
bitset <NMAX> inside;
void read()
{
int x,y;
scanf("%d %d",&n,&m);
for(int i = 0 ; i < m ; i++)
{
scanf("%d %d",&x,&y);
graf[x].push_back(y);
}
}
void dfs(int nod)
{
valinitiala++;
index[nod] = lowlink[nod] = valinitiala;
inside[nod] = true;
stiva.push(nod);
for(vector <int> :: iterator it = graf[nod].begin(); it!= graf[nod].end() ; it++)
{
if( index[*it] == 0)
{
dfs(*it);
lowlink[nod] = min(lowlink[*it],lowlink[nod]);
}
else if(inside[*it] == true)
lowlink[nod] = min(lowlink[*it],lowlink[nod]);
}
if( lowlink[nod] == index[nod])
{
componente++;
int auxnod= stiva.top();
stiva.pop();
inside[auxnod] = true;
solutie[componente].push_back(auxnod);
while(auxnod != nod)
{
auxnod = stiva.top();
inside[auxnod] = true;
solutie[componente].push_back(auxnod);
stiva.pop();
}
}
}
void rezolvare()
{
for(int i = 1 ; i <= n ; i++)
{
if(index[i] == 0)
dfs(i);
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
read();
rezolvare();
printf("%d\n",componente);
for(int i = 1 ; i <= componente; i++)
{
for(vector <int> :: iterator it = solutie[i].begin( ); it != solutie[i].end() ; it++)
printf("%d ",*it);
printf("\n");
}
return 0;
}