#Nelamuriri?
Grafuri orientate
Se numeşte graf orientat sau digraf o pereche ordonată de mulțimi notată G=(V, U), unde:
V este o mulțime finită şi nevidă ale cărei elemente se numesc noduri sau vârfuri;
U este o mulțime de perechi ordonate de elemente distincte din V ale cărei elemente se numesc arce.
V={1,2,3,4,5,6}U={(1,6),(2,1),(2,4),(3,2),(4,2),(5,4),(6,1),(6,4)}
Noțiuni
extremități ale unui arc: pentru arcul u=(x,y), se numesc extremități ale sale nodurile x şi y;
x se numeşte extremitate inițială;
y se numeşte extremitate finală;
y se numește succesor al lui x;
x se numește predecesor al lui y.
vârfuri adiacente: dacă într-un graf există arcul u=(x,y) (sau u=(y,x), sau amândouă), se spune despre nodurile x şi y că sunt adiacente;
incidență:
dacă u1 şi u2 sunt două arce ale aceluiaşi graf, se numesc incidente dacă au o extremitate comună. Exemplu: u1=(x,y) şi u2=(y,z) sunt incidente;
dacă u1=(x,y) este un arc într-un graf, se spune despre el şi nodul x, sau nodul y, că sunt incidente.
Listele de adiacență
Pentru un graf orientat cu G=(V,U) se va memora numărul de noduri n și apoi, pentru fiecare nod x, lista succesorilor lui x, adică nodurilor y cu proprietatea că există arcul (x,y).
Pentru graful alăturat, listele de adiacență sunt:
1: 6
2: 1 4
3: 2
4: 2
5: 4
6: 1 2 4
La reprezentarea în memorie trebui avut în vedere că dimensiunile listelor de succesori sunt variabile. De aceea, este neeficientă utilizarea unor tablouri alocate static. Astfel, putem folosi:
un șir de n tablouri unidimensionale alocate dinamic;
un șir de n vectori din STL;
un șir de n liste simplu (dublu) înlănțuite alocate dinamic.
Probleme
Se da un graf orientat cu n varfuri si m arce prin lista arcelor. Se numeste arc inutil un arc cu proprietatea ca are extremitatile in componente tare conexe diferite. Afisati numarul de arce inutile si care sunt acestea. Exemplu: graf.in 8 11 1 3 3 5 5 7 7 1 2 6 6 8 8 2 1 4 4 6 4 8 4 2 graf.out 4 1 4 4 2 4 6 4 8
Solutie:
//CU COMPONETELE TARE CONEXE
#include <fstream>
using namespace std;
ifstream fin("graf.in");
ofstream fout("graf.out");
int A[101][101],n,m,S[101],P[101],c,k;
void DF_succ(int v, int c)
{
S[v]=c;
for(int i=1;i<=n;i++)
if(!S[i] && A[v][i])
DF_succ(i,c);
}
void DF_pred(int v, int c)
{
P[v]=c;
for(int i=1;i<=n;i++)
if(!P[i] && A[i][v])
DF_pred(i,c);
}
int main()
{
fin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
fin>>x>>y;
A[x][y]=1;
}
for(int i=1;i<=n;i++)
if(!S[i])
{
c++;
DF_succ(i,c);
DF_pred(i,c);
for(int j=1;j<=n;j++)
if(S[j]!=P[j])
S[j]=P[j]=0;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(A[i][j]==1)
if(S[i]!=S[j]) k++;
fout<<k<<endl;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(A[i][j]==1)
if(S[i]!=S[j])
fout<<i<<" "<<j<<endl;
return 0;
}
//CU ROY-WARSHALL
#include <fstream>
using namespace std;
ifstream fin("graf.in");
ofstream fout("graf.out");
int A[101][101],B[101][101],n,m,k;
void RW()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(B[i][j]==0) B[i][j]=B[i][k]*B[k][j];
}
int main()
{
fin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
fin>>x>>y;
B[x][y]=A[x][y]=1;
}
RW();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(A[i][j]==1 && B[j][i]==0) k++;
fout<<k<<endl;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(A[i][j]==1 && B[j][i]==0)
fout<<i<<" "<<j<<endl;
return 0;
}
@-webkit-keyframes swing
{
15%
{
-webkit-transform: translateX(5px);
transform: translateX(5px);
}
30%
{
-webkit-transform: translateX(-5px);
transform: translateX(-5px);
}
50%
{
-webkit-transform: translateX(3px);
transform: translateX(3px);
}
65%
{
-webkit-transform: translateX(-3px);
transform: translateX(-3px);
}
80%
{
-webkit-transform: translateX(2px);
transform: translateX(2px);
}
100%
{
-webkit-transform: translateX(0);
transform: translateX(0);
}
}
@keyframes swing
{
15%
{
-webkit-transform: translateX(5px);
transform: translateX(5px);
}
30%
{
-webkit-transform: translateX(-5px);
transform: translateX(-5px);
}
50%
{
-webkit-transform: translateX(3px);
transform: translateX(3px);
}
65%
{
-webkit-transform: translateX(-3px);
transform: translateX(-3px);
}
80%
{
-webkit-transform: translateX(2px);
transform: translateX(2px);
}
100%
{
-webkit-transform: translateX(0);
transform: translateX(0);
}
}
$red:#F44336;
@mixin transition($in) {
transition:$in;
-webkit-transition:$in;
-moz-transition:$in;
-o-transition:$in;
-ms-transition:$in;
}
@mixin transform($in) {
transform:$in;
-webkit-transform:$in;
-moz-transform:$in;
-o-transform:$in;
-ms-transform:$in;
}
@mixin animation($in) {
animation:$in;
-webkit-animation:$in;
-moz-animation:$in;
-o-animation:$in;
-ms-animation:$in;
}
* {
font-family:Helvetica,sans-serif;
color:$red;
}
.myButt {
outline:none;
border:none;
padding:20px;
display:block;
margin:50px auto;
cursor:pointer;
font-size:20px;
background-color:transparent;
position:relative;
border:2px solid #fff;
@include transition(all 0.5s ease);
}
.four {
overflow:hidden;
span {
color:#fff;
display:inline-block;
@include transition(all 0.3s ease);
}
.icon {
position:absolute;
left:-60px;
top:0;
color:#fff;
padding:20px;
background-color:$red;
@include transition(all 0.3s ease);
}
&:hover {
.icon {
left:0px;
}
span {
color:$red;
margin-left:50px;
}
}
}
$red:#F44336;
@mixin transition($in) {
transition:$in;
-webkit-transition:$in;
-moz-transition:$in;
-o-transition:$in;
-ms-transition:$in;
}
@mixin transform($in) {
transform:$in;
-webkit-transform:$in;
-moz-transform:$in;
-o-transform:$in;
-ms-transform:$in;
}
@mixin animation($in) {
animation:$in;
-webkit-animation:$in;
-moz-animation:$in;
-o-animation:$in;
-ms-animation:$in;
}
body {
margin:0;
padding:0;
background-color:#222;
}
* {
font-family:Helvetica,sans-serif;
color:$red;
}
header {
text-align:center;
h1 {
text-transform:uppercase;
}
}
.myButt {
outline:none;
border:none;
padding:20px;
display:block;
margin:50px auto;
cursor:pointer;
font-size:20px;
background-color:transparent;
position:relative;
border:2px solid #fff;
@include transition(all 0.5s ease);
}
// ################ ONE
.one {
border-color:#fff;
overflow:hidden;
color:#fff;
.insider {
background-color:#fff;
width:100%;
height:20px;
position:absolute;
left:-135px;
@include transform(rotateZ(45deg));
}
&:hover {
background-color:$red;
border-color:#fff;
color:#fff;
.insider {
@include transition(all 0.3s ease);
left:135px;
}
}
}
// ################ TWO
.two {
color:#fff;
&:hover {
border-color:$red;
color:$red;
@include animation(shakeThatBooty 0.3s linear 1);
}
}
@keyframes shakeThatBooty {
33% {
@include transform(rotateZ(10deg));
}
67% {
@include transform(rotateZ(-10deg));
}
100% {
@include transform(rotateZ(10deg));
}
}
// ################ THREE
.three {
color:#fff;
border-color:transparent;
&:before {
width:0;
height:3px;
content:" ";
background-color:$red;
position:absolute;
top:0;
left:50%;
@include transition(all 0.3s ease);
}
&:after {
@extend .three:before;
top:100%;
}
&:hover {
letter-spacing:8px;
color:$red;
&:before {
width:100%;
left:0;
}
&:after {
width:100%;
left:0;
}
}
}
// ################ FOUR
.four {
overflow:hidden;
span {
color:#fff;
display:inline-block;
@include transition(all 0.3s ease);
}
.icon {
position:absolute;
left:-60px;
top:0;
color:#fff;
padding:20px;
background-color:$red;
@include transition(all 0.3s ease);
}
&:hover {
.icon {
left:0px;
}
span {
color:$red;
margin-left:50px;
}
}
}
// ################ FIVE
.five {
overflow:hidden;
color:#fff;
.layer {
color:#fff;
position:absolute;
top:-70px;
width:100%;
left:0;
padding:20px 0;
background-color:$red;
@include transition(all 0.3s ease);
}
&:hover {
.layer {
top:0;
}
}
}
.PM
{
height: 30px;
width: 150px;
background: #676470;
transition:all 0.3s ease;
border-radius: 20px;
}
.PM:hover
{
-webkit-animation: swing 1s ease;
animation: swing 1s ease;
-webkit-animation-iteration-count: 1;
animation-iteration-count: 1;
background:#53a7ea;
}